用c++语言设计算法使用栈实现简单表达式求值

在C++中，我们可以使用栈（Stack）数据结构来设计一个简单的计算器，用于计算基本的算术表达式。这种算法通常称为逆波兰表示法（Reverse Polish Notation, RPN）或后缀表达式的求值。以下是使用栈的基本步骤：

1. **输入处理**：
- 接收用户输入的表达式，通常包含加减乘除操作符和数字。

2. **预处理**：
- 将表达式转换成后缀形式，即将所有的运算符移到它们对应的操作数后面。这一步可以通过双端队列（Deque）辅助完成，从左到右扫描，遇到操作符就将它推入栈，遇到数字则直接读取。

3. **计算过程**：
- 创建一个空栈。遍历后缀表达式，对于每个元素：
- 如果是数字，压入栈；
- 否则是操作符，弹出栈顶的两个数字做相应的运算，结果再压回栈。

4. **最终结果**：
- 当处理完所有元素后，栈顶的数值即为整个表达式的计算结果。

下面是一个简单的C++函数示例：

#include <stack>
#include <string>

int evalRPN(std::string tokens) {
    std::stack<int> numbers;
    for (char token : tokens) {
        if (isdigit(token)) { // 遇到数字，直接压入栈
            numbers.push(token - '0');
        } else { // 遇到运算符
            int second = numbers.top();
            numbers.pop();
            int first = numbers.top();
            numbers.pop();
            switch (token) {
                case '+': numbers.push(first + second); break;
                case '-': numbers.push(first - second); break;
                case '*': numbers.push(first * second); break;
                case '/': {
                    double result = static_cast<double>(first) / second;
                    numbers.push(result);
                    break;
                }
                default: assert(false); // 处理未知运算符
            }
        }
    }
    return numbers.top(); // 返回栈顶结果
}