基于栈的中缀算术表达式求值cpp

基于栈的中缀算术表达式求值通常是通过逆波兰表示法（Reverse Polish Notation, RPN）来实现的，因为栈数据结构非常适合处理这种操作。在C++中，你可以按照以下步骤进行：

1. **输入转换**：首先，你需要将用户输入的中缀表达式转化为RPN。这通常涉及两个栈：一个用于存储操作数，另一个用于存储运算符。遇到操作数就直接压入操作数栈，遇到运算符则比较其优先级，如果当前栈顶运算符优先级低于新运算符，则依次弹出操作数和运算符，直到找到等于或高于新运算符的，然后将新运算符压入栈中。

2. **计算过程**：遍历操作数堆栈，每次取出两个元素，一个是操作数，另一个是运算符。对这两个操作数应用运算符，并把结果推回栈上。这个过程会一直持续到只剩下一个元素为止，即得到最终的结果。

3. **返回结果**：最后的操作数就是表达式的值。

下面是一个简单的示例代码片段，展示了基本的思路：

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

int precedence(char op) {
    // 定义运算符的优先级
    return op == '+' || op == '-' ? 1 : 2;
}

bool isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

std::string infixToRPN(std::string expr) {
    std::stack<char> ops;
    std::string result;
    for (char ch : expr) {
        if (isdigit(ch)) {
            result += ch; // 操作数直接添加到结果中
        } else if (isOperator(ch)) {
            while (!ops.empty() && precedence(ops.top()) >= precedence(ch)) {
                result += ops.top();
                ops.pop();
            }
            ops.push(ch);
        } else if (ch == '(') {
            ops.push(ch);
        } else if (ch == ')') {
            while (ops.top() != '(') {
                result += ops.top();
                ops.pop();
            }
            ops.pop(); // 弹出左括号
        }
    }
    while (!ops.empty()) {
        result += ops.top();
        ops.pop();
    }
    return result;
}

int evaluateRPN(std::string rpn) {
    std::stack<int> stack;
    for (char ch : rpn) {
        if (isdigit(ch)) {
            stack.push(ch - '0'); // 将字符转为数字并压入栈
        } else {
            int right = stack.top(); stack.pop();
            int left = stack.top(); stack.pop();
            switch (ch) {
                case '+': stack.push(left + right); break;
                case '-': stack.push(left - right); break;
                case '*': stack.push(left * right); break;
                case '/': stack.push(left / right); break;
            }
        }
    }
    return stack.top(); // 返回最终结果
}

int main() {
    std::string expr = "4 + 5 * (7 - 9) / 2";
    std::string rpn = infixToRPN(expr);
    int result = evaluateRPN(rpn);
    std::cout << "Result: " << result << std::endl;
    return 0;
}