《算法竞赛进阶指南》0x11 栈 求解中缀表达式

递归求解，首先寻找最后一个加减号，拆分两段，若无最后一个加减号，寻找最后一个乘除号，这时这个表达式中只涉及括号外的乘除法（单个数算在内）。

这个算法实际上就是在将这个表达式分解成含括号的分量和含有乘法的分量，然后再按照乘法分量进行分解。

奉上案例:

1+3*4-(12-1)+20

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000
char s[maxn];
int calc(int l,int r){//递归计算中缀表达式的值 
    for(int i=r,j=0;i>=l;i--){ 
        if(s[i]==')')j--;//j==-1的时候表示i指针正在某个括号中 
        if(s[i]=='(')j++;
        if(!j && s[i]=='+') return calc(l,i-1)+calc(i+1,r);
        if(!j && s[i]=='-') return calc(l,i-1)-calc(i+1,r);
    }
    for(int i=r,j=0;i>=l;i--){//乘除运算符后面没有不在括号中的加减法，优先级最高 
        if(s[i]==')')j--;
        if(s[i]=='(')j++;
        if(!j && s[i]=='*')return calc(l,i-1)*calc(i+1,r);
        if(!j && s[i]=='/')return calc(l,i-1)/calc(i+1,r);
    } 
    //处理完全括号 
    if(s[l]=='(' && s[r]==')')return calc(l+1,r-1);
    //处理单个的数
    int ans=0;
    for(int i=l;i<=r;i++)ans=ans*10+s[i]-'0';
    return ans; 
}
int main(){
    while(cin>>s){
        cout<<calc(0,strlen(s)-1)<<endl;
    }
}