基于栈的后缀算术表达式求值

后缀表达式也被称为逆波兰表达式，是一种不需要括号即可表示算术运算的表达式。例如，中缀表达式"3 + 4 * 2 / ( 1 - 5 )"可以转化为后缀表达式"3 4 2 * 1 5 - / +"。

后缀表达式求值的基本思路是：从左到右扫描表达式，遇到数字就压入栈中，遇到运算符就从栈中弹出两个数进行计算，并将计算结果压入栈中。最后栈中只剩下一个数，就是表达式的计算结果。

以下是基于栈的后缀表达式求值的代码实现：

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

using namespace std;

int evalRPN(string tokens[]) {
    stack<int> st; // 定义一个栈用于存储运算数

    for (int i = 0; i < tokens.size(); i++) {
        if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") { // 遇到运算符
            int op2 = st.top(); st.pop(); // 从栈中弹出两个数
            int op1 = st.top(); st.pop();
            switch (tokens[i][0]) { // 根据运算符进行计算
                case '+': st.push(op1 + op2); break;
                case '-': st.push(op1 - op2); break;
                case '*': st.push(op1 * op2); break;
                case '/': st.push(op1 / op2); break;
            }
        } else { // 遇到数字
            st.push(stoi(tokens[i])); // 将数字压入栈中
        }
    }

    return st.top(); // 最后栈中只剩下一个数，即表达式的计算结果
}

int main() {
    string tokens[] = {"3", "4", "2", "*", "1", "5", "-", "/", "+"};
    int result = evalRPN(tokens);
    cout << "Result: " << result << endl;
    return 0;
}

输出结果为:

Result: 1