C++逆波兰表达式求值

C++中实现逆波兰表达式的求值通常涉及到栈数据结构的应用。逆波兰（RPN，Reverse Polish Notation）也被称为后缀表达式，其特点是从左到右扫描输入表达式，遇到操作数就直接压入栈，遇到运算符则弹出栈顶两个元素进行计算，然后将结果压回栈中。以下是基本步骤：

1. 创建一个空栈。
2. 遍历输入的逆波兰表达式，对于每个元素（可能是操作数或运算符）：
- 如果是操作数，将其压入栈。
- 否则是运算符，从栈中弹出两个操作数，根据运算符进行相应的算术运算（如加、减、乘、除等），并将结果压回栈中。
3. 循环结束后，栈中只剩下一个元素，这就是表达式的最终结果。

C++代码示例：

#include <stack>
#include <string>

int evalRPN(std::vector<std::string>& tokens) {
    std::stack<int> stack;
    for (const auto& token : tokens) {
        if (isdigit(token[0])) { // 操作数
            stack.push(stoi(token));
        } else { // 运算符
            int op2 = stack.top(); stack.pop();
            int op1 = stack.top(); stack.pop();
            switch (token) {
                case "+": stack.push(op1 + op2); break;
                case "-": stack.push(op1 - op2); break;
                case "*": stack.push(op1 * op2); break;
                case "/": stack.push((double)op1 / op2); break; // 注意处理除法可能得到整数的情况
                default: throw std::invalid_argument("Invalid operator");
            }
        }
    }
    return stack.top(); // 返回最终结果
}

// 使用示例
std::vector<std::string> tokens{"2", "1", "+", "3", "*"};
int result = evalRPN(tokens);