c++波兰表达式求值

波兰表达式是一种前缀表达式，它将操作符写在操作数之前。例如，表达式 2 + 3 可以写为 + 2 3。

求解波兰表达式的方法是使用栈。从右往左扫描表达式，如果遇到一个数字，则将其压入栈中。如果遇到一个操作符，则从栈中弹出两个数字，执行相应的计算，将结果压入栈中。最终，栈中只会剩下一个数字，即表达式的值。

下面是一个用 C++ 实现的波兰表达式求值的例子：

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

using namespace std;

int evaluate(string expr) {
    stack<int> s;
    for (int i = expr.size() - 1; i >= 0; i--) {
        if (isdigit(expr[i])) {
            s.push(expr[i] - '0');
        } else {
            int op1 = s.top();
            s.pop();
            int op2 = s.top();
            s.pop();
            switch (expr[i]) {
                case '+': s.push(op1 + op2); break;
                case '-': s.push(op1 - op2); break;
                case '*': s.push(op1 * op2); break;
                case '/': s.push(op1 / op2); break;
            }
        }
    }
    return s.top();
}

int main() {
    string expr = "+ * 2 3 4";
    int result = evaluate(expr);
    cout << "Result: " << result << endl;
    return 0;
}

在这个例子中，我们将波兰表达式 "+ * 2 3 4" 传递给 evaluate 函数进行求值，结果为 10。