递归求解表达式计算问题

表达式计算4

https://ac.nowcoder.com/acm/problem/50999

雨神告诉俺们，表达式计算用递归最不容易出错。（确实不递归的话需要考虑的情况就很多了，容易错漏）
本题解参考牛友 id 唯爱奕希依然 的代码。

题目描述

给出一个表达式,其中运算符仅包含+,-,*,/,^（加减乘整除乘方）要求求出表达式的最终值

数据可能会出现括号情况，还有可能出现多余括号情况

数据保证不会出现 $\geq 2^{31}$ 的答案（ps：说明可以用int存结果）

数据可能会出现负数情况（ps：这里指的有负数情况下负数会用括号括起来）

输入描述:

仅一行，即为表达式

输出描述:

仅一行，既为表达式算出的结果

示例

输入

(2+2)^(1+1)

输出

备注:

表达式总长度 $\leq 30$

题目分析

（~~不想看分析的话，题目小结和完整代码在最后卑微.jpg~~）

首先考虑没有括号的情况：比如
如果表达式的输入不存在括号，就直接按照运算符优先级进行计算就可以了。这里我们借助递归来简单化代码，减少出错。

注意递归的运算使用了栈，即LIFO后入先出的容器。所以运算符优先级最高应该最先计算的^应该最后入栈！！！

代码：（题解末尾会讨论储存符号的变量初值能否设置为0的问题，这里建议暂停思考一下）

string n;//存储表达式
int cale(int left, int right){
    //计算表达式n中，下标left~right的部分
    int add = 0, mul = 0, power = 0;//记录三种运算符，它们的下标不可能是0 故可以使用0来初始化 
    for(int i = left; i <= right; i++){
        switch(n[i]){//记录各种优先级符号的位置，便于后面计算
           case '+':
           case '-':
               add = i;
           case '*':
           case '/':
               mul = i;
           case '^':
               power = i;
           }
    }
    if(add)//开始计算，注意运算符优先级最低的应该放在最前面
        if(n[add] == '+')
            return cale(l, add-1) + cale(add+1, r);
        else
            return cale(l, add-1) - cale(add+1, r);
    if(mul)
        if(n[mul] == '*')
            return cale(l, mul-1) * cale(mul+1, r);
        else
            return cale(l, mul-1) / cale(mul+1, r);
    if(power)//优先级最高的最后计算
        return pow(cale(l, power-1), cale(power+1, r));
    }

递归计算表达式的思想就结束了。是不是超级简单！！

接下来就是考虑括号的细节问题了，我们以示例为例：(2+2)^(1+1)
如果存在括号，这一段被括号括起来的表达式(2+2)和(1+1)应该最先计算对吧？同样由于我们使用的是栈，为了先计算，就应该最后入栈。就是说在代码处理的时候可以先忽略括号内部表达式的存在，最后再对括号内部进行处理。

所以我们稍微更改一下上面统计符号的方法：只记录不被括号包住的运算符^

    int cnt = 0, add = 0, mul = 0, power = 0;//cnt记录括号个数
    for(int i = l; i <= r; i++){
        if(n[i] == '(')
            cnt++;
        else if(n[i] == ')')
            cnt--;//匹配掉前面的括号
        else if(!cnt){  
        //只记录括号外的符号
            switch(n[i]){
            case '+':
            case '-':
                add = i;
            case '*':
            case '/':
                mul = i;
            case '^':
                power = i;
            }
        }
    }

如上所示，第一次记录的符号就只有^了，也就是它会。

乘幂运算以后我们再处理括号里面的内容对吧？也就是递归到只剩下括号里面的内容的时候：判断一下当前表达式左右是否为一对括号，是则去除括号，计算括号的内部：

        if(n[l] == '(' && n[r] == ')')
            return cale(l + 1, r - 1);

但是这个步骤不可以放在递归函数的开头，否则样例(2+2)^(1+1)的左右括号就会被当成一对给拆成2+2)^(1+1了！！

上述步骤应该只在当前表达式左右括号匹配的情况下才进行。也就是只在只剩下一对括号包裹一个表达式的(2+2)的时候才进行。那么如何判断是否匹配？利用之前的符号记录吧！因为我们前面只记录括号外面的符号，如果括号外面没有符号，不就说明只剩下一个括号内的表达式了吗？！：

    if(!cnt && !add && !mul && !power){
        //剩下的式子都包在括号里，则去掉括号计算。注意这里的代码要放在符号记录之后
        if(n[l] == '(' && n[r] == ')')
            return cale(l + 1, r - 1);
    }

哦哦！不过还存在一种没有符号记录且cnt==0的情况：当前表达式只剩下数字。

所以需要在这个条件语句里面加进去一个语句来返回这个纯数字（实际上这个函数才是我们递归的deadline基线条件）

注意纯数字有可能有多位，而我们使用的是字符串来储存多位数字，不可直接返回。应该写一个函数调用来处理多位数字。

int number(int left, int right){
//返回数组n的下标[left, right]段组成的数字
    int ans = 0;
    for(int i = left; i <= right; i++)
        ans = ans * 10 + n[i] - '0';//高位部分乘以10再加下一个位的数字，注意-'0'将字符n[i]从ascii码转为数字
    return res;
}

程序是不是就完成了呢？我们最后再读一遍题目确保一下没有被漏掉的条件。哦哦！！居然还有可能出现多余的括号。那就去掉多余括号，就完事了！故记录符号以后的括号处理完整代码是这样的：

    if(cnt > 0 && n[l] == '(')//去掉多余的左括号
        return cale(l + 1, r);
    else if(cnt < 0 && n[r] == ')')//去掉多余的右括号
        return cale(l, r - 1);
    else if(!cnt && !add && !mul && !power){
        if(n[l] == '(' && n[r] == ')') //剩下的式子完全包在括号里
            return cale(l + 1, r - 1);
        return number(l, r);// 或者 只剩下一个数字
    }

思路小结与完整代码

遍历一遍表达式，记录下括号的匹配情况cnt和括号外的三种优先级的运算符位置 add mul power
处理括号：
a. 多余的括号去掉，递归计算去掉以后的部分。
b. 只剩下一串由括号包裹的表达式的时候也直接去掉括号，递归计算里面的表达式。
c. 注意 (cnt add mul power均为0的时候) 这时内部剩下的表达式有可能只有一个数字，用一个函数返回这个数字。
按照第1步记录的符号位置，递归计算剩下的内容

#include<bits/stdc++.h>
using namespace std;
string n;
int number(int left, int right){
    //返回字符串n中[left,right]段的数字
    int ans = 0;
    for(int i = left; i <= right; i++)
        ans = ans * 10 + n[i] - '0';
    return ans;
}
int cale(int l, int r){
    int cnt = 0, add = 0, mul = 0, power = 0;
    for(int i = l; i <= r; i++){
        if(n[i] == '(')
            cnt++;
        else if(n[i] == ')')
            cnt--;
        else if(!cnt){  //记录括号外的最后一个符号位置，优先级不同的分开记录
            switch(n[i]){
            case '+':
            case '-':
                add = i;
            case '*':
            case '/':
                mul = i;
            case '^':
                power = i;
            }
        }
    }
    if(cnt > 0 && n[l] == '(')//去掉多余的括号
        return cale(l + 1, r);
    else if(cnt < 0 && n[r] == ')')
        return cale(l, r - 1);
    else if(!cnt && !add && !mul && !power){
        //剩下的式子包在括号里或者只剩下数字，则获取这个数字
        if(n[l] == '(' && n[r] == ')')
            return cale(l + 1, r - 1);
        return number(l, r);
    }
    if(add)
        if(n[add] == '+')
            return cale(l, add-1) + cale(add+1, r);
        else
            return cale(l, add-1) - cale(add+1, r);
    if(mul)
        if(n[mul] == '*')
            return cale(l, mul-1) * cale(mul+1, r);
        else
            return cale(l, mul-1) / cale(mul+1, r);
    if(power)
        return pow(cale(l, power-1), cale(power+1, r));
}
int main(){
    cin>>n;
    cout<<cale(0,n.length()-1)<<endl;
    return 0;
}

代码到这里其实已经可以ac了，但是在听雨神讲这道题的时候评论区里讨论了一下符号标志到底能不能被初始化为0。

符号标志的意思是标记这个符号在字符串中的下标，所以应该被初始化为一个不可能的位置。但逻辑上说运算符号是不会出现在第一位也就是n[0]的。但是考虑到负数出现在第一位的话，-这个符号可能作为负号出现在n[0]。比如-2+1这样的样例上述代码是无法正常计算的。俺的代码能过只是运气而已。

顺带一提上述代码并不是遇到负数就挂了，而是遇到位于首位的负号会挂。因为首位一旦出现负号，则将带着负号进入number处理函数，故会出错。但如果表达式带的是中间的负数（如3+(-2)或者(-2)+1）会被当做表达式处理成0-2=-2。也是侥幸能过的一个原因吧

综上所述，数组中不可能出现的下标还是标记为-1吧检讨.jpg