表达式求值

需要处理的问题

1. 如何确定运算符的优先级
   • 使用unordered_map确定不同运算符的优先级
2. 怎么处理数字
   • 遍历至数字时，说明接下来的是数字，通过简单的处理就可以获得当前字符对应的数字
3. 怎么处理括号
   • 遇见左括号时候，让左括号入栈
   • 遇见右括号时，不断的进行计算，直至运算符栈中只剩下左括号
   • 令左括号出栈
4. 当运算符优先级不同的时候怎么处理
   • 当栈顶运算符的优先级大于等于当前遍历至的运算符，则可以进行计算，再令当前的运算符入栈
   • 当栈顶运算符的优先级小于当前遍历至的运算符，则可以进行

示例：\(5+3*(12 + 4)/4-8\)

代码：

#include <iostream>
#include <unordered_map>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
stack<int> num;
stack<char> op;

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

int main(){
    unordered_map<char, int> pr{{'+',1}, {'-',1}, {'*', 2}, {'/',2}};
    //确定运算的优先级
    string str;
    cin >> str;

    for(int i = 0;i < str.size();i++){
        auto c = str[i];
        if(isdigit(c)){         //如果是数字
            int x = 0, j = i;
            while(j < str.size() && isdigit(str[j]))    //继续统计完整的数字
                x = x * 10 + str[j++] - '0';
            i = j - 1;
            num.push(x);            //入栈
        }
        else if(c == '(') op.push(c);   //做括号，则入栈
        else if(c == ')') {             //右括号，则计算至左括号
            while(op.top() != '(') eval();
            op.pop();}                  //左括号出栈
        else{                       //如果是运算符
            while(op.size()         //运算符栈不为空
                && op.top() != '('  //运算符栈顶不为左括号
                && pr[op.top()] >= pr[c]) eval();   //当前符号的优先级小于运算符栈顶
            op.push(c);             //当前运算符入栈
        }
    }

    while(op.size()) eval();        //运算剩余
    cout << num.top() << endl;
    return 0;
}