中缀表达式和逆波兰表达式

1.中缀表达式

1）标准四则运算的表达式就叫中缀表达式

2.逆波兰表达式

1）逆波兰表达式（后缀表达式）：字符串中只有数字和运算符，没有括号，所有运算符号位于操作数之后

3.中缀表达式转逆波兰表达式

1）运算符优先级：乘除大于加减，右括号必须匹配左括号

2）遍历中缀表达式，遇到数字，输出到后缀表达式

3）遇到运算符：

先判断栈是否为空，若是，则直接将此操作符压入栈
若为'('，入栈；
若为')'，把栈顶符号至 '(' 之间的符号依次出栈加入到后缀表达式，'('直接出栈不加入后缀表达式，')'不入栈也不加入后缀表达式；
若为乘除加减，要入栈的运算符优先级大于栈顶运算符的优先级，直接入栈，否则（小于等于），栈顶运算符出栈加入到后缀表达式，再次比较，重复上述过程，直到出现优先级小于自己的运算符成为栈顶，自己再入栈；

4）中缀表达式为空时，栈中符号依次出栈加入到后缀表达式，直到栈为空

vector<string> toRPN(string s)
{
    vector<string> RPN;
    stack<string> sta;
    int n = s.size();
    for (int i = 0; i < n; ++i)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            long long num = 0;//long long防止越int界
            while (i < n && s[i] >= '0' && s[i] <= '9')
                num = 10 * num + s[i++] - '0';
            --i;
            RPN.push_back(to_string(num));
        }
        else if (s[i] == '+' || s[i] == '-')//加和减优先级比较低
        {
            while (!sta.empty() && (sta.top() == "*" || sta.top() == "/" || sta.top() == "+" || sta.top() == "-"))
            {
                RPN.push_back(sta.top());
                sta.pop();
            }
            s[i] == '+' ? sta.push("+") : sta.push("-");
        }
        else if (s[i] == '*' || s[i] == '/')
        {
            while (!sta.empty() && (sta.top() == "*" || sta.top() == "/"))
            {
                RPN.push_back(sta.top());
                sta.pop();
            }
            s[i] == '*' ? sta.push("*") : sta.push("/");
        }
        else if (s[i] == '(')
            sta.push("(");
        else if (s[i] == ')')
        {
            while (sta.top() != "(")
            {
                RPN.push_back(sta.top());
                sta.pop();
            }
            sta.pop();
        }
    }
    while (!sta.empty())//把栈中剩余的string全部写到RPN中
    {
        RPN.push_back(sta.top());
        sta.pop();
    }
    return RPN;
}

4.逆波兰表达式求值

1）遇到数字就放入栈中

2）遇到运算符operator就依次取出栈的上面两个元素a2,a1，然后a1 operator a2得出计算结果，再把计算结果放入栈中；

3）遍历到表达式中的最后一个运算符operator时，把计算结果直接取出就是所求结果；

4）注意一种特殊情况：一般的逆波兰表达式最后一个是运算符，但是如：{"18"}，此时就应该直接取出；

class Solution {
public:
    int evalRPN(vector<string>& tokens)
    {
        if (tokens.size() == 1)//处理如{"18"}这种特殊情况
            return stoi(tokens[0]);
        stack<int> sta;
        int index = 0, res = 0;
        for (string str : tokens)
        {
            if (str != "+" && str != "-" && str != "*" && str != "/")
                sta.push(stoi(str));
            else//遇到运算符
            {
                int a2 = sta.top();
                sta.pop();
                int a1 = sta.top();
                sta.pop();
                if(str=="+")
                    sta.push(a1 + a2);
                else if(str=="-")
                    sta.push(a1 - a2);
                else if(str=="*")
                    sta.push(a1 * a2);
                else if(str == "/")
                    sta.push(a1 / a2);
            }
        }
        return sta.top();
    }
};

5.前缀表达式

1）前缀表达式又称波兰表达式，字符串中只有数字和运算符，没有括号，前缀表达式的运算符位于操作数之前