1. 定义

• 前缀表达式：+ab，称为波兰式
• 中缀表达式：a+b，正常写的表达式，将运算符写在两个操作数中间的表达式，称作中缀表达式。在中缀表达式中，运算符有不同的优先级，圆括号用于改变运算顺序，这使得运算规则比较复杂，求值过程不能直接从左到右顺序进行，不利于计算机处理。
• 后缀表达式：ab+，称为逆波兰式，将运算符写在两个操作数之后的表达式称作后缀表达式。后缀表达式中没有括号，并且运算符没有优先级。后缀表达式的求值过程能够严格按照从左到右的顺序进行，有利于计算机处理。

例：

中缀：(3+4)×5-6

前缀：- x + 3 4 5 6

后缀：3 4 + 5 x 6 -

2. 相互转换

2.1 中缀→前缀

这里使用入栈法解决，后续会提到表达式树的方法，步骤如下：

1. 初始化两个栈：运算符栈s1，操作数栈s2
2. 从右向左扫描中缀表达式
3. 遇到操作数压入栈s2
4. 遇到运算符时，与栈顶运算符比较优先级
   • 若s1为空，或栈顶运算符为右括号，则直接入栈
   • 否则比较运算符优先级，若优先级比较高或者相等，直接入栈s1
   • 否则将s1栈顶的运算符弹出并压入到s2中，在此转到4-1与新栈顶元素比较
5. 遇到括号时：
   • 如果是右括号”)”，直接压入
   • 如果是左括号”(”，以此弹出s1栈顶的运算符直到遇到右括号为止。
6. 重复2~5，直到最左边
7. 将s1的剩余运算符压入s2
8. 以此弹出s2中的元素，结果为前缀表达式

void in_to_pre_expression(string s)
{
    stack<char> s1,s2;// s1运算符
    for(int i=s.size()-1;i>=0;i--)
    {
        if(s[i]>='0'&&s[i]<='9')
            s2.push(s[i]);
        else{
            if(s[i]!='(')
            {
                if(s1.empty()||s[i]==')'||s1.top()==')')
                    s1.push(s[i]);
                else if(Operator_Priority(s[i])>=Operator_Priority(s1.top()))
                {
                    s1.push(s[i]);
                }
                else if(Operator_Priority(s[i])<Operator_Priority(s1.top())){
                    while(!s1.empty()&&Operator_Priority(s[i])<Operator_Priority(s1.top()))
                    {
                        s2.push(s1.top());
                        s1.pop();
                    }
                    s1.push(s[i]);
                }
            }
            else
            {
                while(s1.top()!=')')
                {
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.pop();
            }
        }
    }
    while(!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    while(!s2.empty())
    {
        std::cout<<s2.top()<<" ";
        s2.pop();
    }
}

后缀表达式求值

class Solution {
public:
    int calculateNum(int x,int y,string op)
    {
        char ch=op[0];
        switch(ch)
        {
            case '+':
                return x+y;
            case '-':
                return x-y;
            case '*':
                return x*y;
            case '/':
                return x/y;
        }
        return 0;
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto &i:tokens)
        {
            if(i=="+"||i=="-"||i=="*"||i=="/")
            {
                int x=st.top();
                st.pop();
                int y=st.top();
                st.pop();
                st.push(calculateNum(y,x,i));  //顺序不能搞错
            }
            else
                st.push(stoi(i));
        }
        
        return st.top();
    }
};

2.2 中缀→后缀

中缀转后缀与中缀转前缀方法类似，只不过是从左向右

void in_to_post_expression(string s)
{
    stack<char> s1, s2; // s1运算符
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
            s2.push(s[i]);
        else
        {
            if (s[i] != ')')
            {
                if (s1.empty() || s1.top() == '(' || s[i] == '(')
                    s1.push(s[i]);
                else if (Operator_Priority(s[i]) >= Operator_Priority(s1.top()))
                    s1.push(s[i]);
                else if (Operator_Priority(s[i]) < Operator_Priority(s1.top()))
                {
                    while (!s1.empty() && Operator_Priority(s[i]) < Operator_Priority(s1.top()))
                    {
                        s2.push(s1.top());
                        s1.pop();
                    }
                    s1.push(s[i]);
                }
            }
            else
            {
                while (!s1.empty() && s1.top() != '(')
                {
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.pop();
            }
        }
    }
    while (!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    while (!s2.empty())
    {
        std::cout << s2.top() << " ";
        s2.pop();
    }
}

前缀表达式求值就是从右向左扫描前缀表达式，后缀是从左向右