题解 | #表达式求值#

#include<iostream>
#include<stack>
using namespace std;

string opt = "+-*/";
bool isPriority(char top, char curr){
    if(top == '('){
        return false;
    }else if((top == '+' || top == '-') && (curr == '*' || curr == '/')){
        return false;
    }
    
    return true;
}

void computer(stack<int>& st1, stack<char>& st2){
    int num1 = st1.top();
    st1.pop();
    int num2 = st1.top();
    st1.pop();
    char ch = st2.top();
    st2.pop();
    if(ch == '+') st1.push(num2 + num1);
    else if(ch == '-') st1.push(num2 - num1);
    else if(ch == '*') st1.push(num2 * num1);
    else if(ch == '/') st1.push(num2 / num1);
}

int main(){
    string str;
    while(cin >> str){
        stack<int> st1;
        stack<char> st2;
        st2.push('(');
        str.push_back(')');
        
        bool flag = false;
        for(int i=0; i<str.length(); i++){
            if(str[i] == '('){
                st2.push('(');
            }else if(str[i] == ')'){
                // 可能是 "()"
                while(st2.top() != '('){
                    computer(st1, st2);
                }
                st2.pop();
            }else if(opt.find(str[i]) != opt.npos && flag){
                while(isPriority(st2.top(), str[i])){
                    computer(st1, st2);
                }
                st2.push(str[i]);
                flag = false;
            }else{
                int num = 0;
                while(i < str.size() && isdigit(str[i])){
                    num = num * 10 + str[i] - '0';
                    i++;
                }
                
                st1.push(num);
                i--;
                flag = true;
            }
        }
        
        cout << st1.top() << endl;
    }
    
    return 0;
}