本贴是y总讲解的笔记，供自己复习

首先复习一下后缀表达式

Leetcode 150. 逆波兰表达式求值

首先引入了表达式树（内节点都是运算符，叶节点都是数字），后缀表达式是表达式树的后序遍历。不必真的建树、遍历，可以用栈实现递归的效果。
后序遍历以左右根的方式遍历，当遍历到运算符的时候，前面2个元素就是左右子树。因此可以从左至右遍历，遇到数字则压入栈中，遇到运算符则弹出2个数做运算，最后栈中元素就是表达式的结果。

时间复杂度

遍历序列$o(n)$,入栈出栈$o(1)$,因此时间复杂度$o(n)$。

C++ 代码

class Solution {
public:

    stack<int> stk;
    void eval(string s){
    // 注意顺序，a先入栈，因此后出
        int b=stk.top();stk.pop();
        int a=stk.top();stk.pop();
        if(s=="+") stk.push(a+b);
        else if(s=="-") stk.push(a-b);
        else if(s=="*") stk.push(a*b);
        else stk.push(a/b);
    }

    int evalRPN(vector<string>& tokens) {
        unordered_set<string> op={"+","-","*","/"};
        for(auto& s:tokens){
            if(op.count(s)) eval(s);
            else stk.push(stoi(s));
        }
        return stk.top();
    }
};

返回本题

中缀表达式遍历到根节点还需遍历右子树，因此需要2个栈，分别存数和运算符。子树遍历完需要算出该子树的值。若当前遍历到的运算符<=上一个运算符的优先级，则表明已遍历完该子树，此时需要计算子树的值。
括号单独考虑：遇到'('入栈，直到遇到')'，从右往左计算该括号对内部的表达式。

PS. 表达式树中没有括号，括号只表示优先级，不影响树的结构

C++ 代码

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

using namespace std;

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

unordered_map<char,int> pr={{'+',1},{'-',1},{'*',2},{'/',2}};

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(){
    string s;
    cin>>s;

    for(int i=0;i<s.size();i++)
    {
        char c=s[i];
        if(isdigit(c))
        {
            int j=i,x=0;
            while(j<s.size() && isdigit(s[j]))
            {
                x=x*10+s[j]-'0';
                j++;
            }
            num.push(x);
            i=j-1;
        }
        else if(c=='(') op.push(c);
        else if(c==')')
        {
            while(op.top()!='(') eval();
            op.pop();
        }
        else
        {
            while(op.size() && pr[c]<=pr[op.top()]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();

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

    return 0;
}

中缀转后缀，当前元素优先级<=栈顶元素优先级，出栈
中缀转前缀：当前元素优先级<栈顶元素优先级，出栈（从后向前扫描）

参考文献

春季每日一题：
https://www.bilibili.com/video/BV12f4y1s7V4?p=3