利用栈实现简单算数表达式求值c++

利用栈（Stack）实现简单算术表达式求值通常涉及到逆波兰表示法（Reverse Polish Notation, RPN），也被称为后缀表达式。C++中通过迭代器遍历输入字符串，并使用两个栈分别处理操作符和操作数：

1. **解析输入表达式**：将中缀表达式转换成后缀表达式，遇到数字直接压入操作数栈，遇到运算符则将其推到运算符栈。

2. **计算求值**：从后往前遍历后缀表达式的每个元素，当遇到一个数字时，弹出最近的运算符并进行相应的运算（如加减乘除），然后将结果压回操作数栈。这个过程一直持续到只剩下一个元素。

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

std::string precedence(char op) {
    if (op == '+' || op == '-') return "left";
    if (op == '*' || op == '/') return "right";
}

int applyOp(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 注意这里需要判断除数是否为零
    }
}

int evaluate(std::string tokens) {
    std::stack<int> values;
    std::stack<char> ops;

    for (char token : tokens) {
        if (isdigit(token)) {
            values.push(stoi(token));
        } else {
            while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
                int val2 = values.top(); values.pop();
                int val1 = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            ops.push(token);
        }
    }

    while (!ops.empty()) {
        int val2 = values.top(); values.pop();
        int val1 = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        values.push(applyOp(val1, val2, op));
    }

    return values.top();
}

int main() {
    std::string expression = "4 + 5 * 6"; // 示例表达式
    std::cout << "Result of expression: " << evaluate(expression) << std::endl;
    return 0;
}