后缀表达式

给定一个表达式，其中运算符仅包含 +、-、*、/，可能包含括号，请你求出表达式的最终值。

数据保证给定的表达式合法。
题目保证 - 只作为减号出现，不会作为负号出现。
题目保证所有的数字均为正整数。
题目保证运算过程以及结果中，均不超过 \(2^{31} - 1\)。
题目中的整除是指向 \(0\) 取整，c++ 的整除默认就是向 \(0\) 取整：-3.2 = -3, 3.2 = 3

像我们平常使用的表达式 (4 + 2 * 30) / 8 + 2 就是「中缀表达式」，要用代码实现求值得将中缀表达式转成「后缀表达式」或者叫「逆波兰表示法」：4 2 30 * + 8 / 2 +。

有了后缀表达式后怎么求值？

初始化栈 st3

从后缀表达式的前面一直往后边扫描

遇到「数 num」丢入栈 st3

遇到「符号 op」，依次从栈 st3 中取出元素 \(b, a\)，将「a op b」的结果丢入栈 st3 内（要特别留意取出的顺序，是先取出 \(b\)，再取出 \(a\)）

后缀表达式求值举例

4 2 30 * + 8 / 2 +

st1	表达式
4 2 30	* + 8 / 2 +
4 60	+ 8 / 2 +
64	8 / 2 +
64 8	/ 2 +
8	2 +
8 2	+
10	none

如何将「中缀表达式」转成「后缀表达式」？

初始化栈 st1、st2

从中缀表达式的左边一直扫描到后面

遇到「数字」直接丢入栈 st1 中

遇到「 ( 」直接丢入栈 st2 中

遇到「 ) 」将 st2 的栈顶符号依次取出并丢进栈 st1 中，知道遇到 ( 为止，并丢弃 (

遇到「符号」先将栈顶 st2 的符号依次取出并丢进栈 st1 中，直到遇到的符号为 ( 或者遇到的符号运算优先级更低为止。

扫描完成后不要忘记将 st2 栈中滞留的符号依次取出丢入栈 st1 中。

「中缀」转「后缀」再求值代码参考

// 即使是不成熟的尝试，

int sti(const string &s)
{
    int ans = 0;
    for (auto x : s) ans *= 10, ans += x - '0';
    return ans;
}

int calc(int a, int b, int op)
{
    if (op == '*') return a * b;
    if (op == '/') return a / b;
    if (op == '-') return a - b;
    if (op == '+') return a + b;
}

// 优先级
int pri(int op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
}

queue<string> RPN(const string& s)
{
    queue<string> st1; 
    stack<string> st2;
    int p = 0;
    while (p < s.size())
    {
        if (s[p] >= '0' && s[p] <= '9')
        {
            int l = p; 
            while (p + 1 < s.size() && s[p + 1] >= '0' && s[p + 1] <= '9') p ++;
            st1.push(string(s.begin() + l, s.begin() + ++p));
        }
        else if (s[p] == '(') st2.push("("), p ++;
        else if (s[p] == ')') 
        {
            while (st2.top() != string("("))
            {
                st1.push(st2.top()); st2.pop();
            }
            st2.pop(); p ++;
        }
        else
        {
            while (st2.size() && st2.top() != string("(") && pri(st2.top()[0]) >= pri(s[p]))
            {
                st1.push(st2.top()); st2.pop();
            }
            st2.push(string() + s[p ++]);
        }
    }
    while (st2.size()) 
    {
        st1.push(st2.top()); st2.pop();
    }
    return st1;
}

int value(queue<string> st1)
{
    stack<int> st2;
    while (st1.size())
    {
        string t = st1.front(); st1.pop();
        // cout << t << "  "; // 输出后缀表达式
        if (t[0] >= '0' && t[0] <= '9')
        {
            st2.push(sti(t));
        }
        else
        {
            int a, b; 
            b = st2.top(); st2.pop();
            a = st2.top(); st2.pop();
            st2.push(calc(a, b, t[0]));
        }
    }
    return st2.top();
}

string s;

void solve(void) 
{
    cin >> s;
    cout << value(RPN(s)) << endl;
}

// 也胜于胎死腹中的策略。

「中缀」边转边求值代码参考

int sti(const string &s)
{
    int ans = 0;
    for (auto x : s) ans *= 10, ans += x - '0';
    return ans;
}

int calc(int a, int b, int op)
{
    if (op == '*') return a * b;
    if (op == '/') return a / b;
    if (op == '-') return a - b;
    if (op == '+') return a + b;
}

// 优先级
int pri(int op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
}

int RPN(const string& s)
{
    int p = 0;
    stack<int> st1, st2;
    while (p < s.size())
    {
        if (s[p] >= '0' && s[p] <= '9')
        {
            int l = p; 
            while (p + 1 < s.size() && s[p + 1] >= '0' && s[p + 1] <= '9') p ++;
            st1.push(sti(string(s.begin() + l, s.begin() + ++p)));
        }
        else if (s[p] == '(') st2.push(s[p ++]);
        else if (s[p] == ')')
        {
            while (st2.top() != '(')
            {
                int op = st2.top(); st2.pop();
                int b = st1.top(); st1.pop();
                int a = st1.top(); st1.pop();
                st1.push(calc(a, b, op));
            }
            st2.pop(); p ++;
        }
        else
        {
            while (st2.size() && st2.top() != '(' && pri(st2.top()) >= pri(s[p]))
            {
                int op = st2.top(); st2.pop();
                int b = st1.top(); st1.pop();
                int a = st1.top(); st1.pop();
                st1.push(calc(a, b, op));
            }
            st2.push(s[p ++]);
        }
    }
    while (st2.size())
    {
        int op = st2.top(); st2.pop();
        int b = st1.top(); st1.pop();
        int a = st1.top(); st1.pop();
        st1.push(calc(a, b, op));
    }
    return st1.top();
}

string s;

void solve(void) 
{
    cin >> s;
    cout << RPN(s) << endl;
}