题解 | #表达式求值# 栈的应用

#include <iostream>
#include <string>
#include <stack>
using namespace std;
/*1)数字入一个栈，符号入一个栈。2）用函数判断符号的优先级，新来的符号优先级大于栈底的符号优先级时，3）函数：从数字栈取两个数字出来计算，并将结果再压回栈中*/
void Compute(stack<int>&num,stack<char>&op){
    if(num.empty()||op.empty()) return;
    int b=num.top();
    num.pop();
    int a=num.top();
    num.pop();
    char op0=op.top();
    op.pop();
    if(op0=='+'){a=a+b;}
    else if(op0=='-'){a=a-b;}
    else if(op0=='*'){a=a*b;}
    else if(op0=='/'){a=a/b;}
    num.push(a);

}
bool priority(char m,char n){//m是栈顶的符号，n是遍历到的符号
    if(m=='('){return false;}
    else if((m=='+'||m=='-')&&(n=='*'||n=='/')){return false;}
    return true;
}
int main() {
string s;
while(cin>>s){
stack<int> num;
stack<char> op;
op.push('(');
s+=')';//给整个表达式加一个大括号，号一起判断优先级
bool flag=false;//flag用来判断符号是计算用的还是标志正负号用的。true时，说明数字已经出现了，跟在数字后的，一定是符号，把这个符号判断完优先级计算完之后应该入栈并将flag=false。flag=false，表示符号已经出现了，如果下一个还是符号，说明这是正负号。如果下再个是数字，找完了数字，入了数字栈，再将flag=true
for(int i=0;i<s.size();i++){
    if(s[i]=='('){op.push('(');}
    else if(s[i]==')'){
        while(!op.empty()&&op.top()!='('){
        Compute(num,op);}
        op.pop();//弹出左括号
    }
    else if(!op.empty()&&flag){//flag=true时，数字过完了，当前是运算符，判断优先级
        while(priority(op.top(),s[i])){//比较运算符的优先级
            Compute(num,op);
        }
        op.push(s[i]);
        flag=false;//符号走过了，下一个该数字了
    }
    else if(!op.empty()&&!flag){
        //flag=false时，数字还没有来，下一个是数字，判断数字有没有正负号
        int j=i;
        if(s[j]=='+'||s[j]=='-'){
            i++;//当前是正负号，去找下一个数字
        }
        while(i<s.size()&&isdigit(s[i])){i++;}//直到数字走完，到数字的下一位
        string tmp=s.substr(j,i-j);
        num.push(stoi(tmp));//把数字存入数字栈
        i--;//因为下一趟循环还会有i++，先减回来
        flag=true;//数字走过了，下一个是符号了
    }
}
cout<<num.top()<<endl;
}
}

注意！！！不确定栈里有没有东西时不要乱输出！！！可能会因为你输出了一个空栈的栈顶导致溢出！！！！！！！！！