利用栈实现表达式求值

好的，这是一个很常见的问题。基本思路是利用两个栈，一个用来存储数字，另一个用来存储运算符。具体步骤如下：

1.遍历表达式中的每个字符，如果是数字则直接入数字栈；如果是运算符，则与运算符栈栈顶元素进行比较，如果当前运算符优先级低于栈顶运算符，则将栈顶运算符弹出，并从数字栈中弹出两个数字进行计算，然后将计算结果压入数字栈中，直到当前运算符优先级高于等于栈顶运算符，然后将当前运算符入栈。

2.当遍历完表达式后，如果运算符栈中还有元素，则从数字栈中弹出两个数字进行计算，然后将计算结果压入数字栈中，直到运算符栈为空。

3.最终，数字栈中的唯一元素就是表达式的求值结果。

下面是一个实现例子（假设表达式中只包含 +、-、*、/ 四种运算符）：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int evaluateExpression(string expr) {
    stack<int> nums; // 存储数字的栈
    stack<char> ops; // 存储运算符的栈
    int num = 0; // 用来存储多位数字

    for (int i = 0; i < expr.length(); i++) {
        if (isdigit(expr[i])) { // 如果是数字，则存储到 num 中
            num = num * 10 + (expr[i] - '0');
        }
        else { // 如果是运算符
            nums.push(num); // 将之前存储的数字压入数字栈
            num = 0; // 重置 num

            while (!ops.empty() && (ops.top() == '*' || ops.top() == '/') &&
                   (expr[i] == '+' || expr[i] == '-')) { // 如果栈顶运算符优先级高于等于当前运算符，则进行计算
                int b = nums.top(); nums.pop();
                int a = nums.top(); nums.pop();
                char op = ops.top(); ops.pop();
                if (op == '*') nums.push(a * b);
                else if (op == '/') nums.push(a / b);
            }

            ops.push(expr[i]); // 将当前运算符入栈
        }
    }

    nums.push(num); // 将最后一个数字压入数字栈

    while (!ops.empty()) { // 将剩余的运算符和数字进行计算
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
        else if (op == '/') nums.push(a / b);
    }

    return nums.top(); // 返回最终结果
}

int main() {
    string expr = "3+5*2-8/4";
    cout << evaluateExpression(expr) << endl; // 输出结果为 12
    return 0;
}