所有的表达式都可以画为一颗树，计算数为叶子节点，计算符为中间节点；不同顺序的表达式就是树的不同顺序遍历形式

1.后缀表达式—逆波兰表达式

不需要考虑运算优先级，树的后序遍历，每次计算父节点时，左右孩子已经得到结果， 不需要记录运算符；

利用栈来模拟运算过程，不需要真正建树；

遇到运算数就放入栈中，遇到运算符则从栈顶弹出两个运算数进行运算，并将结果压入栈中；

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

stack<int> stk;

int main()
{
    string str;
    cin >> str;

    for(int i = 0;i < str.size();i ++)
    {
        char c = str[i];

        if(isdigit(c)) stk.push(c - '0');
        else
        {
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();

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

    }

    cout << stk.top() << endl;

    return 0;
}

2.中缀表达式

需要考虑运算优先级的问题；

树的遍历方式是 左根右 ，当向上走时，说明该节点已经计算完成，向下走时，说明该节点还未被计算；

需要记录运算符；

在树上，运算符优先级小的在上面，优先级大的在下面；

当前运算符优先级小于上一个运算符的优先级时，则必须先将上一个运算符计算完（向上走）， 当前运算符优先级大于上一个运算符时，向下走，直接放入栈中

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

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    // 由于栈先进后出的性质，a为倒数第二个数，b为倒数第一个数，因为顺序回影响减法和除法
    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 j = i, x = 0;
            while(j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++] - '0';
            i = j - 1; // 更新i的位置
            num.push(x);
        }
        else if(c == '(') op.push(c);
        else if(c == ')')
        {
            while(op.top() != '(') eval();
            op.pop(); // 把'('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;
}