波兰表达式的c++算法

波兰表达式（Polish Notation），也称为逆波兰表示法，是一种数学运算符排列的方式，它的运算符位于操作数之后，不需要使用括号来确定优先级。在C++中，处理这种类型的表达式通常涉及使用栈数据结构。

处理波兰表达式的一般算法步骤如下：

1. 创建一个空栈。
2. 遍历输入的波兰表达式字符流：
- 如果遇到数字，压入栈中。
- 如果遇到运算符，弹出两个最近的数字，进行相应的运算，并将结果压回栈中。
3. 当遍历完所有字符后，栈中剩下的就是最终计算的结果。

C++中可以使用STL中的stack容器来实现这个过程。例如，你可以定义一个函数接受一个字符串，然后递归地处理每个元素，同时维护一个栈来存储中间结果。

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

int applyOperation(char op, int b, int a) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: throw std::runtime_error("Invalid operator");
    }
}

std::string polishNotation(std::string exp) {
    std::stack<int> stack;
    for (char c : exp) {
        if (isdigit(c)) {
            stack.push(c - '0'); // 将字符转为整数并压入栈
        } else {
            int b = stack.top(); stack.pop();
            int a = stack.top(); stack.pop();
            stack.push(applyOperation(c, b, a));
        }
    }
    return to_string(stack.top()); // 返回最终结果
}

int main() {
    std::string expression = "4 2 + 3 *";
    std::cout << "Result of the expression is: " << polishNotation(expression) << '\n';
    return 0;
}