题解29：https://ac.nowcoder.com/acm/problem/50999

听说这是递归的及格之作?[doge]

前言：首先我们要知道要处理几种的特殊情况：

1.(((3+5)^(1+1)

2.(3+5)))^(1+1)

3.(3+5)^(((1+1)

4.(3+5)^(1+1)))

分别对应开头，末尾，中间右边和中间左边位置的括号

思路&AC代码：

#include<iostream>
#include<cmath>//pow()
#include<string>
using namespace std;
string s;
int tonum(int l, int r)
{
    int num=0;
    for(int i=l; i<=r; ++i)
    {
        num=num*10+s[i]-'0';//类比二进制的sum=(sum<<1)+x,十进制进一位就是*10，例如45=0*10+4+(0*10+4)*10+5
    }
    return num;
}
int calc(int l, int r)
{
    int pos1=-1,pos2=-1,pos3=-1,cnt=0;
  //因为递归，要先考虑最低级的计算，再一层一层回归到结果，而一般的计算符从左到右计算，先左后右，所以最后面出现的那个运算符级别低，但+低于*低于^
    for(int i=l; i<=r; ++i)
    {
        if (s[i] == '(') {cnt++;}
        else if (s[i] == ')') {cnt--;}
      //当cnt==0已经出现一个完整括号，那么下次一开始统计的已经在括号外面后了，现在开始统计最低级的运算符所在的位置。
      //例如（32+12）+（1+1）+（2+3），先统计到第一个两个括号之间的+，遇到下一个左括号停止统计（cnt>0），然后统计第二三括号之间的+，因为第三个括号右面没东西了(当cnt又==0）时,这样就先统计到括号外面的了（括号里面优先级高一些，不是我们现在想要的）
        else if ( (s[i] =='+' || s[i] == '-') && cnt == 0 ) {pos1=i;}
        else if ( (s[i] =='*' || s[i] == '/') && cnt == 0 ) {pos2=i;}
        else if (s[i] == '^' && cnt == 0) {pos3=i;}
    }
    
    if (pos1 == -1 && pos2 ==-1 && pos3 == -1)
    {
        if(cnt == 0 && s[l] == '(' ) {return calc(l+1, r-1);}//cnt==0说明括号没有出错，最多只是多余，如（（56））那么一层一层扔掉括号，如果一次全扔完（扔cnt个），那么有可能处理不了一些特殊情况
        else if(cnt > 0 ) {return calc(l+1, r);}//说明左括号多了对应前言中的情况1和3（注意左边那个符合标准已经拆开了，这次处理的是右边括号多余的），还是只能一层一层扔
        else if(cnt < 0 ) {return calc(l,r-1);}//说明左括号多了对应前言中的情况2（注意左边那个符合标准已经拆开了，这次处理的是右边括号多余的）和4，还是只能一层一层扔
        else return tonum(l,r);//说明cnt == 0且没有括号了，那么将字符转化为数字，有人会想那-5怎么办，其实-5不属于这种情况，如（-5），pos1不会-1，会转化成calc('('/*注意这里不是传字符串，只是把传的字符串写出来方便理解*/)-calc(5);calc('(')会return 0,则变为0-5等于-5（int）
    }
  	//下面的情况括号也匹配了，也找到最低级的运算符了，开始计算
    else if (pos1 != -1)
    {
        if (s[pos1] == '+') {return calc(l, pos1-1) + calc(pos1+1, r);}//表达式左右两边的为数值，下同
        else {return calc(l, pos1-1) - calc(pos1+1, r);}
    }
    else if (pos2 != -1)
    {
        if (s[pos2] == '*') {return calc(l, pos2-1) * calc(pos2+1, r);}
        else {return calc(l, pos2-1) / calc(pos2+1, r);}
    }
    else {return pow( calc(l, pos3-1), calc(pos3+1, r) );}       
  	return 0;//不写这一句（如果输入“（-5）”会发生未定义行为），calc('(')时会自动return 0（devc++中最后一条赋值语句（int cnt =0），为没有人为return时的默认返回值）;
}
int main()
{
    cin>>s;
    cout<<calc(0,s.length()-1);
    return 0;
}