P丹3《每日一题·春季 笔记本》 详细题解见笔记本P3
其他人的题解1

不用建树，而是用中缀表达式自己的性质，使用栈达到递归的效果

如何判断某棵子树被遍历完了？
当前运算符优先级 <= （上一个）栈顶运算符优先级，表示子树已遍历完，可求出值（可操作）

模板

 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'; // 特别容易忘记j++ ！！！
            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() && pr[op.top()] >= pr[c]) eval();
            op.push(c); // 也容易忘记 ！！！！
        }
    }

    while (op.size()) eval();
    cout << num.top() << endl;

完整代码

#include <iostream>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;
/*
void eval() {
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();

    if (c == '+') num.push(a + b);
    else if (c == '-') num.push(a - b);
    else if (c == '*') num.push(a * b);
    else num.push(a / b);
}*/

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}}; // hash表定义各运算符优先级
    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'; // 特别容易忘记j++ ！！！
            i = j - 1; // 因为for循环结束会i++，所以不是i=j，一定要更新i，因为j已经将连续的数字遍历过了
            num.push(x);
        } 
        else if (c == '(') op.push(c); //左括弧直接进op栈
        else if (c == ')') {
            while (op.top() != '(') eval();
            op.pop(); // 不要忘记将左括号( 弹出运算符栈 ！！！ 肯定是遇到了栈顶是左括弧所以while才结束，故要将左括弧出栈，留在栈中没有用
        }
        else { // 一般运算符 + - * / 等
            while (op.size() && pr[op.top()] >= pr[c]) eval(); // 满足优先级要求则出来做操作
            op.push(c); // 也容易忘记 ！！！！ // op栈 为空，或者不满足优先级要求则直接进op栈
        }
    }

    while (op.size()) eval(); //枚举完str后，把所有没有操作完的运算符从右往左操作一遍即可
    cout << num.top() << endl; // 最后num栈中剩下的数就是答案
    return 0;
}