中缀表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值，其中 - 只做二元运算符。

链接：AcWing 3302。

将一个运算符入栈前，如果先前的运算符优先级比这个高或者同级，那么之前的运算符一定可以运算；如果优先级比它低那么无法判断。对于括号，遇到右括号时将栈中所有表达式求解，直到遇到左括号即可。

考虑 3 * 2 + 4，当遇到加法时已经可以将 3 * 2 计算出来了；而 3 + 2 * 4，并不能判断这个乘法能不能先计算。

至于优先级，可以用表存储，也可以开一个大小足够的数组，实测数组比哈希表快了一倍，所以用数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

// 开大点无所谓，不用想它们对应的 ASCII 值
int pr[128];
char s[100010];
stack<int> nums;
stack<char> ops;

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

int main() {
    pr['+'] = pr['-'] = 1;
    pr['*'] = pr['/'] = 2;
    cin >> s;
    for (int i = 0; s[i]; i++) {
        char ch = s[i];
        if (isdigit(ch)) {
            int j = i, x = 0;
            while (s[j] && isdigit(s[j]))
                x = x * 10 + s[j++] - '0';
            nums.push(x);
            // 别忘了更新 i 到这个数字的末尾
            i = j-1;
        } else if (ch == '(') {
            ops.push(ch);
        } else if (ch == ')') {
            while (ops.top() != '(') eval();
            // 把左括号扔掉
            ops.pop();
        } else {
            while (ops.size() && pr[ops.top()] >= pr[ch]) eval();
            ops.push(ch);
        }
    }
    
    while (ops.size()) eval();
    cout << nums.top() << endl;

    return 0;
}