C++利用栈进行表达式求值

使用栈计算表达式的一般方法是将中缀表达式转换为后缀表达式，然后再用后缀表达式计算结果。下面是一个简单的 C++ 代码实现：

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

using namespace std;

// 判断是否为数字
bool isDigit(char c) {
    return c >= '0' && c <= '9';
}

// 判断是否为运算符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取运算符优先级
int getPriority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

// 计算两个数的结果
int calculate(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

// 将中缀表达式转换为后缀表达式
string toPostfix(string infix) {
    stack<char> s;
    string postfix;
    for (int i = 0; i < infix.size(); i++) {
        char c = infix[i];
        if (isDigit(c)) { // 数字直接输出
            postfix += c;
        } else if (isOperator(c)) { // 运算符入栈，遇到优先级更低的运算符就弹出
            while (!s.empty() && isOperator(s.top()) && getPriority(s.top()) >= getPriority(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        } else if (c == '(') { // 左括号直接入栈
            s.push(c);
        } else if (c == ')') { // 右括号弹出栈顶元素直到遇到左括号
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if (!s.empty()) {
                s.pop();
            }
        }
    }
    while (!s.empty()) { // 将剩余的运算符弹出
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

// 计算后缀表达式的结果
int evaluatePostfix(string postfix) {
    stack<int> s;
    for (int i = 0; i < postfix.size(); i++) {
        char c = postfix[i];
        if (isDigit(c)) { // 数字入栈
            s.push(c - '0');
        } else if (isOperator(c)) { // 弹出栈顶的两个数进行计算，并将结果入栈
            int b = s.top();
            s.pop();
            int a = s.top();
            s.pop();
            s.push(calculate(a, b, c));
        }
    }
    return s.top();
}

// 计算中缀表达式的结果
int evaluateInfix(string infix) {
    string postfix = toPostfix(infix);
    return evaluatePostfix(postfix);
}

int main() {
    string infix = "3+4*5/(2-1)";
    cout << infix << " = " << evaluateInfix(infix) << endl; // 输出结果为 23
    return 0;
}

上述代码中，`toPostfix` 函数将中缀表达式转换为后缀表达式，`evaluatePostfix` 函数计算后缀表达式的值，`evaluateInfix` 函数计算中缀表达式的值。这里使用了两个栈，一个栈用于将运算符转换为后缀表达式，另一个栈用于计算后缀表达式的值。