题解 | #四则运算# 字符串运算式转换为逆波兰表达式

整个题解分为2部分，第一部分是根据输入的字符串表达式，构建出逆波兰表达式；第二步是根据给出的逆波兰表达式求具体值。

第一部分是难点，需要考虑到负号与负数的影响，当负号之前为括号或者没有任何符号时，不能直接入栈减号(通过开头补 0 消除)，也要考虑到自然数存在大于个位数的情况，比如 100 放入栈中不是 1，0，0 这三个数。设立一个字符串 vector 存储逆波兰表达式结果，数字直接 push_back，遇到运算符先放入临时的 stack 中，后续再放入 vector 中汇总。

当第一部分构建完毕后，根据得到的逆波兰表达式数组很容易求出最终的结果，也是通过栈来实现。

代码如下，相关注释已经写全。

#include <iostream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

int main() {
    string s;
    int res;
    while (getline(cin, s)) {
        vector<string> v;
        stack<char> st;
        stack<int> st1;
        // 第一部分：构建出逆波兰表达式数组 v
        // 构建原则：遇到括号与乘除无条件入栈，遇到加减把栈顶的乘除加减都弹出后再入栈(遵循运算顺序)
        // 注意减号，当其前面为括号或者是无符号(i = 0)时，需要补充一个 0，不然需要当作负数处理，入栈时该数需添加负号
        for (int i = 0; i < s.size(); i++) {
            // 遇到括号与乘除无条件入栈
            if (s[i] == '(' || s[i] == '[' || s[i] == '{' || s[i] == '*' || s[i] == '/') st.push(s[i]);
            else if (s[i] == '+' || s[i] == '-') {
                // 减号前面为括号或者是无符号(i = 0)时，需要补充一个 0
                if ((i == 0 || s[i - 1] == '(' || s[i - 1] == '[' || s[i - 1] == '{') && s[i] == '-') {
                    v.push_back("0");
                    st.push(s[i]);
                }
                else {
                    // 遇到加减把栈顶的乘除加减都弹出后再入栈(遵循运算顺序)
                    while (!st.empty() && (st.top() == '*' || st.top() == '/' || st.top() == '+' || st.top() == '-')) {
                        if (st.top() == '*') v.push_back("*");
                        else if (st.top() == '/') v.push_back("/");
                        else if (st.top() == '+') v.push_back("+");
                        else v.push_back("-");
                        st.pop();
                    }
                    st.push(s[i]);
                }
            }
            // 遇到右括号就一直弹出栈顶元素直至栈顶元素为左括号
            else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
                while (st.top() != '(' && st.top() != '[' && st.top() != '{') {
                    if (st.top() == '+') v.push_back("+");
                    else if (st.top() == '-') v.push_back("-");
                    else if (st.top() == '*') v.push_back("*");
                    else v.push_back("/");
                    st.pop();
                }
                // 弹出栈顶的左括号
                st.pop();
            }
            // 这里需要考虑自然数大于个位数的情况，比如 100 不能视作 3 个数而应该是单个数
            else {
                string tmp;
                // 0-9 的 ASCII 码为 48-57
                while (i < s.size() - 1 && s[i + 1] >= 48 && s[i + 1] <= 57) tmp += s[i++];
                // 这里 i + 1不满足时退出循环还需要再加当前的 i 因为当前的 i 是满足的
                tmp += s[i];
                v.push_back(tmp);
            }
        }
        // 最后依次弹出栈内所有元素
        while (!st.empty()) {
            if (st.top() == '+') v.push_back("+");
            else if (st.top() == '-') v.push_back("-");
            else if (st.top() == '*') v.push_back("*");
            else v.push_back("/");
            st.pop();
        }
        // 第二部分：逆波兰表达式求值
        // 依次序读取 vector 中的逆波兰表达式各个项，数字就入栈，字符就弹出 2 个执行操作后入栈
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == "+" || v[i] == "-" || v[i] == "*" || v[i] == "/") {
                int tmp3;
                int tmp1 = st1.top();
                st1.pop();
                int tmp2 = st1.top();
                st1.pop();
                if (v[i] == "+") tmp3 = tmp2 + tmp1;
                else if (v[i] == "-") tmp3 = tmp2 - tmp1;
                else if (v[i] == "*") tmp3 = tmp2 * tmp1;
                else tmp3 = tmp2 / tmp1;
                st1.push(tmp3);
            }
            else st1.push(stoi(v[i]));
        }
        // 最后栈顶的元素即为最终值
        res = st1.top();
        st1.pop();
        cout << res << endl;
    }
    return 0;
}