算术表达式求值(栈)c++

算术表达式求值通常涉及到逆波兰表示法（Reverse Polish Notation, RPN）或者中缀表达式的转换，利用C++中的栈数据结构可以实现这个过程。以下是一个简单的步骤：

1. **输入表达式**：首先需要接收用户输入的数学表达式，如"3 + 4 * 5"。

2. **预处理**：将中缀表达式转换成后缀表达式（RPN），这一步通过递归右结合规则完成，即将操作符放在其操作数之后。例如上述表达式会变成"3 4 5 * +"。

3. **初始化栈**：创建一个空的堆栈，用于存储操作数。

4. **遍历RPN表达式**：从左到右扫描每个元素，如果遇到数字就压入栈，如果遇到运算符则弹出两个栈顶元素进行运算并把结果压回栈里。

5. **计算**：当遍历完RPN表达式后，栈内只剩下一个元素，即为最终的结果。

6. **返回结果**：从栈中弹出结果即可。

#include <stack>
#include <string>

int evalPostfix(std::string& postfix) {
    std::stack<int> stack;
    for (char c : postfix) {
        if (isdigit(c)) {
            stack.push(c - '0'); // 数字直接压栈
        } else {
            int op2 = stack.top(); // 弹出栈顶的数
            stack.pop();
            int op1 = stack.top(); // 再次弹出栈顶的数
            switch (c) {
                case '+': stack.push(op1 + op2); break;
                case '-': stack.push(op1 - op2); break;
                case '*': stack.push(op1 * op2); break;
                case '/': stack.push(op1 / op2); break;
            }
        }
    }
    return stack.top();
}

int main() {
    std::string expr = "3 4 5 * +";
    int result = evalPostfix(expr);
    std::cout << "Result is: " << result << std::endl;
    return 0;
}