题解 | #Groundhog and 2-Power Representation#

核心思路：

这个题目的数据范围很吓人 1e180，c++肯定需要使用高精度;
但是经过推算发现pow(2 , 600)正好是 1e180;
所以只有最后一步需要使用高精度。

具体步骤：

第一步：分组，例如可以将示例分为:
["(2(2+2(0))+2)", "(2(2+2(0)))", "(2(2)+2(0))", "(0)"]

string s; cin >> s;
int count = 0;
vector<string> nums;

for(int i = 0; i < s.size(); i ++)
{
  if(s[i] == '('){
    str = "(";
    int cnt = 1 , j = i + 1;
    while(cnt > 0){
      str += s[j];
      if(s[j] == ')') cnt --;
      if(s[j] == '(') cnt ++;
      j ++;
    }
    i = j - 1;
    count ++;
    nums.push_back(str);
  }

第二步：用栈计算刚刚每个组的值:
如果遇到后括号 ) ，循环弹出栈，直到遇到前括号 ( ，中途遇到加号 + 则进行加法运算，遇到前括号则变为2的次方(cnt = pow(2 , cnt))；
(注：整数转字符串，因为栈存储的数字串是倒着的，所以转换完也应该是倒着的)
例如示例计算完的结果为：[10 , 8 , 5 , 0]。

vector<int> res;

void soval(string str){
    stack<char> zhan;
    for(int i = 0 ; i < str.size() ; i ++)
    {
        if(str[i] == ')'){
            string cnt = "";
            while(zhan.top() != '('){
                if(zhan.top() == '+'){
                    zhan.pop();
                    int t = s_i(cnt) + s_i(f(zhan));
                    cnt = i_s(t);
                }
                else{
                    cnt += zhan.top();
                    zhan.pop();
                }
            }
            if(zhan.size() >= 2){
                zhan.pop();
                zhan.pop();
                cnt = i_s(pow(2 , s_i(cnt)));
                for(int i = cnt.size() - 1 ; i >= 0 ; i --)
                    zhan.push(cnt[i]);
            }
            else{
                res.push_back(s_i(cnt));
                break;
            }
        }
        else{
            zhan.push(str[i]);
        }
    }
}

第三步：使用高精度计算pow(2 , 上述各结果)的和。

string ans = "";

for(auto i : res){
	ans = add(ans , mup(i));
}

第四步：统计分组后2的个数:
最后结果 += [(2的个数 - 分组个数) X 2]。

用到的工具函数：\

字符串转整型：

int s_i(string str){
    reverse(str.begin() , str.end());
    int ans = 0;
    for(int i = 0 ; i < str.size() ; i ++)
    {
        ans = ans * 10 + (str[i] - '0');
    }
    return ans;
}

整型转字符串：

string i_s(int u){
    string ans = "";
    while(u){
        ans += (u % 10 + '0');
        u /= 10;
    }
    return ans;
}

取栈里的值：

string f(stack<char> &zhan)
{
    string ans = "";
    while(zhan.top() >= '0' && zhan.top() <= '9'){
        ans += zhan.top();
        zhan.pop();
    }
    return ans;
}

高进度加法：

string add(string a , string b)
{
    reverse(a.begin() , a.end());
    reverse(b.begin() , b.end());
    int flag = 0;
    string c = "";
    for(int i = 0 ; i < max(a.size() , b.size()) ; i ++)
    {
        int x = 0 , y = 0;
        if(i < a.size()) x = a[i] - '0';
        if(i < b.size()) y = b[i] - '0';
        c += (x + y + flag) % 10 + '0';
        flag = (x + y + flag) / 10;
    }
    if(flag) c += flag + '0';
    reverse(c.begin() , c.end());
    return c;
}

2的次方：

string mup(int u)
{
    string ans = "1";
    for(int i = 0 ; i < u  ; i ++){
        ans = add(ans , ans);
    }
    return ans;
}

AC代码

#include <iostream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

using ll = long long;
const int N = 1010;
vector<string> nums;
vector<int> res;

string i_s(int u){
    string ans = "";
    while(u){
        ans += (u % 10 + '0');
        u /= 10;
    }
    return ans;
}

int s_i(string str){
    reverse(str.begin() , str.end());
    int ans = 0;
    for(int i = 0 ; i < str.size() ; i ++)
    {
        ans = ans * 10 + (str[i] - '0');
    }
    return ans;
}

string f(stack<char> &zhan)
{
    string ans = "";
    while(zhan.top() >= '0' && zhan.top() <= '9'){
        ans += zhan.top();
        zhan.pop();
    }
    return ans;
}

void soval(string str){
    stack<char> zhan;
    for(int i = 0 ; i < str.size() ; i ++)
    {
        if(str[i] == ')'){
            string cnt = "";
            while(zhan.top() != '('){
                if(zhan.top() == '+'){
                    zhan.pop();
                    int t = s_i(cnt) + s_i(f(zhan));
                    cnt = i_s(t);
                }
                else{
                    cnt += zhan.top();
                    zhan.pop();
                }
            }
            
            if(zhan.size() >= 2){
                zhan.pop();
                zhan.pop();
                cnt = i_s(pow(2 , s_i(cnt)));
                for(int i = cnt.size() - 1 ; i >= 0 ; i --)
                    zhan.push(cnt[i]);
            }
            else{
                res.push_back(s_i(cnt));
                break;
            }
        }
        else{
            zhan.push(str[i]);
        }
    }
}

string add(string a , string b)
{
    reverse(a.begin() , a.end());
    reverse(b.begin() , b.end());
    int flag = 0;
    string c = "";
    for(int i = 0 ; i < max(a.size() , b.size()) ; i ++)
    {
        int x = 0 , y = 0;
        if(i < a.size()) x = a[i] - '0';
        if(i < b.size()) y = b[i] - '0';
        c += (x + y + flag) % 10 + '0';
        flag = (x + y + flag) / 10;
    }
    if(flag) c += flag + '0';
    reverse(c.begin() , c.end());
    return c;
}

string mup(int u)
{
    string ans = "1";
    for(int i = 0 ; i < u  ; i ++){
        ans = add(ans , ans);
    }
    return ans;
}

int main()
{
    string s;
    cin >> s;
    int count = 0;
    string str = "";
    int yu = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] == '('){
            str = "(";
            int cnt = 1 , j = i + 1;
            while(cnt > 0){
                str += s[j];
                if(s[j] == ')') cnt --;
                if(s[j] == '(') cnt ++;
                j ++;
            }
            i = j - 1;
            count ++;
            nums.push_back(str);
        }
        else{
            if(s[i] == '2')
                yu ++;
        }
    }
    
    for(auto i : nums)
        soval(i);
    
    string ans = i_s(2 * (yu - nums.size()));
    for(auto i : res)
        ans = add(ans , mup(i));
    cout << ans;
    return 0;
}