利用中缀表达式实现表达式求值

原理：给出中缀表达式，求出表达式的值。利用栈来模拟表达式树的操作。

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

stack<int> nums;
stack<char> op;

void eval() {
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    auto c = op.top(); op.pop();
    if(c == '+') nums.push(a + b);
    else if(c == '-') nums.push(a - b);
    else if(c == '*') nums.push(a * b);
    else if(c == '/') nums.push(a / b);
}

int main(){
    string str;
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    cin >> str;
    for(int i = 0; i < str.size(); i++) {
        auto c = str[i];
        if(isdigit(c)) {
            int x = 0, j = i;
            //处理组合数，比如123
            while(isdigit(str[j])) 
                x = x * 10 + str[j++] - '0';
            i = j - 1;
            nums.push(x);
        } 
        else if(c == '(') op.push(c);
        else if(c == ')') {
          	//在遇到（之前，计算
            while(op.top() != '(') eval();
            op.pop();
        } 
        else {
          	//如果当前栈顶运算符的优先级大于现在的运算符，那就计算栈内的两个元素
          	//用while而不用if的原因是比如计算(1-2*3+4)，在c为+的时候，要计算前面的三个数字。如果用if做不到。
          	//特判断op.size()是防止访问了空栈的元素
            while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();
    cout << nums.top();
}