C++进阶之路系列将会与题目录系列一起继续我的C++学习，欢迎订阅专栏：C++系列

引言：我们进行计算机的使用时，使用的是中缀表达式。中缀表达式符合我们日常的逻辑计算。但对于计算机来说，想要识别中缀表达式的顺序却是件不容易的事情。在这里我们引出了逆波兰表达式（后缀表达式）来解决这一问题。

逆波兰表达式

相关题目：逆波兰表达式求值
简要介绍：

逆波兰表达式是一种后缀表达式，由波兰数学家扬・武卡谢维奇于 1920 年提出，核心特点是运算符位于操作数之后（区别于日常使用的 “中缀表达式”，如a + b），无需括号即可明确表示运算优先级，广泛应用于计算机编译、计算器（如经典的 HP 计算器）等场景。

要实现计算器这个功能，第一步就是实现计算器能看懂的（后缀表达式）的计算。

计算规则

逆波兰表达式的计算依赖栈这种 “先进后出” 的数据结构，步骤简单且固定：
从左到右扫描表达式的每个元素（操作数或运算符）；
若遇到操作数，直接压入栈中；
若遇到运算符，从栈中弹出最顶端的两个操作数（注意：先弹出的是 “右操作数”，后弹出的是 “左操作数”）；
用该运算符对两个操作数进行计算，将结果重新压入栈中；
扫描结束后，栈中剩余的唯一元素即为最终结果。

---

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for (size_t i = 0; i < tokens.size(); ++i) {
        const string& str = tokens[i];
        if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
            s.push(stoi(str));
        } else {
            int right = s.top();
            s.pop();
            int left = s.top();
            s.pop();
            switch (str[0]) {
            case '+':
                s.push(left + right);
                break;
            case '-':
                s.push(left - right);
                break;
            case '*':
                s.push(left * right);
                break;
            case '/':
                s.push(left / right);
                break;
            }
        }
    }
    return s.top();
}

1. 功能：计算后缀表达式的值。
2. 参数：
   tokens：后缀表达式，存储为字符串向量。
3. 逻辑：
   使用一个栈 s 来存储操作数。
4. 遍历 tokens：
   如果当前元素是数字，则将其转换为整数并压入栈。
   如果当前元素是运算符，则从栈中弹出两个操作数（右操作数和左操作数），根据运算符进行计算，并将结果压入栈。
5. 最后，栈顶的值即为表达式的计算结果。

中缀转后缀

这里通过toRPN函数来实现这个功能。
核心上来讲主要要注意对数字 计算符 以及 括号的处理
这里使用一个输出型参数vector< string >来接受后缀表达式。

---

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

void toRPN(const string& s, size_t& i, vector<string>& v) {
    stack<char> st;
    while (i < s.size()) {
        if (isdigit(s[i])) {
            string num;
            while (i < s.size() && isdigit(s[i])) {
                num += s[i];
                ++i;
            }
            v.push_back(num);
        } else {
            if (s[i] == '(') {
                i++;
                toRPN(s, i, v);
            } else if (s[i] == ')') {
                i++;
                while (!st.empty()) {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
                return;
            } else {
                if (st.empty() || _operatorPrecedence[s[i]] >
                                          _operatorPrecedence[st.top()]) {
                    st.push(s[i]);
                    i++;
                } else {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
            }
        }
    }
    while (!st.empty()) {
        v.push_back(string(1, st.top()));
        st.pop();
    }
}

1. 功能：将中缀表达式转换为后缀表达式（RPN，Reverse Polish Notation）。
2. 参数：
   s：输入的字符串表达式。
   i：当前处理的字符索引。
   v：存储后缀表达式的向量。
3. 逻辑：

遍历字符串 s，根据当前字符的类型进行不同处理：

• 数字：将连续的数字字符拼接成一个完整的数字字符串，并将其添加到结果向量 v 中。
  左括号 ‘(’：递归调用 toRPN，处理括号内的表达式。
  右括号 ‘)’：将栈中的运算符依次弹出并添加到结果向量 v 中，直到遇到左括号。
• 运算符：
  如果栈为空，或者当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符压入栈。
  否则，将栈顶运算符弹出并添加到结果向量 v 中，然后继续比较当前运算符和新的栈顶运算符。
• 最后，将栈中剩余的运算符依次弹出并添加到结果向量 v 中。

计算逻辑

这里需要对传入的中缀表达式进行处理，由于传入的字符串之中含有空格这一多余字符，我们首先就是要将空格去除。其次就是对于负数的处理，在我们对负数进行处理时，需要对‘-’进行分情况讨论，讨论其为负号，还是减号。

int calculate(string s) {
    std::string s1;
    s1.reserve(s.size());
    for (auto e : s) {
        if (e != ' ') {
            s1 += e;
        }
    }
    s.swap(s1);
    s1.clear();
    for (size_t i = 0; i < s.size(); ++i) {
        if (s[i]== '-' && (i == 0 || !isdigit(s[i - 1]) || s[i - 1] != ')')) {
            s1 += "0-";
        } else {
            s1 += s[i];
        }
    }

    size_t i = 0;
    vector<string> v;
    toRPN(s1, i, v);
    return evalRPN(v);
}

1. 功能：计算输入字符串表达式的值。
2. 逻辑：
   去除空格：将输入字符串 s 中的空格去除。
   处理负数：在表达式中，如果 - 出现在表达式的开头，或者前一个字符不是数字且不是右括号，则将其视为负数的开始，插入一个 0。
   转换为后缀表达式：调用 toRPN 方法将处理后的字符串转换为后缀表达式。
   计算后缀表达式的值：调用 evalRPN 方法计算后缀表达式的值并返回。

总结

通过实现三个函数来对计算器进行了模拟实现，三个函数分开独立实现各自功能，提高了各自独立性，耦合度降低。