用c++语言中的栈实现简单表达式求值并给出代码

在 C++ 中，我们可以使用栈（Stack）来实现简单的表达式求值，例如逆波兰表示法（Reverse Polish Notation，RPN）。这种方法也被称为后缀表示法，因为操作数在操作符之后。这样可以避免括号的复杂处理。

首先，我们需要定义两个栈：一个用于存储操作数，另一个用于临时存放操作符。然后遍历输入的表达式，根据遇到的字符（数字或运算符）来执行相应的操作：

1. 对于数字，直接压入操作数栈。
2. 遇到运算符时，从操作数栈弹出两个操作数，并对它们进行运算（如加减乘除），将结果压回操作数栈，同时移动运算符到临时栈。
3. 当遍历完所有字符后，如果还有运算符留在临时栈里，需要继续进行运算。

下面是一个简单的 C++ 示例代码实现：

#include <stack>
#include <string>

int eval(std::string tokens) {
    std::stack<int> numStack;
    std::stack<char> opStack;

    for (char token : tokens) {
        if (isdigit(token)) {
            int num = 0;
            while (isdigit(token)) {
                num = num * 10 + token - '0';
                ++token;
            }
            numStack.push(num);
        } else if (token == '+' || token == '-' || token == '*' || token == '/') {
            while (!opStack.empty() && hasPrecedence(token, opStack.top())) {
                int right = numStack.top();
                numStack.pop();
                int left = numStack.top();
                numStack.pop();
                char op = opStack.top();
                opStack.pop();

                switch (op) {
                    case '+':
                        numStack.push(left + right);
                        break;
                    case '-':
                        numStack.push(left - right);
                        break;
                    case '*':
                        numStack.push(left * right);
                        break;
                    case '/':
                        if (right != 0)
                            numStack.push(left / right);
                        else
                            throw std::runtime_error("Division by zero");
                        break;
                }
            }
            opStack.push(token);
        }
    }

    // Handle any remaining operators
    while (!opStack.empty()) {
        int right = numStack.top();
        numStack.pop();
        int left = numStack.top();
        numStack.pop();
        char op = opStack.top();
        opStack.pop();

        switch (op) {
            case '+':
                numStack.push(left + right);
                break;
            case '-':
                numStack.push(left - right);
                break;
            case '*':
                numStack.push(left * right);
                break;
            case '/':
                numStack.push(left / right);
                break;
        }
    }

    return numStack.top();  // Return the final result
}

bool hasPrecedence(char op1, char op2) {
    if (op2 == '(' || op2 == ')') return false;  // Ignore parentheses
    if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) return true;
    return op1 > op2;
}

// Usage example
std::string expression = "2 3 + 4 *";
int result = eval(expression);
std::cout << "Result: " << result << std::endl;