用 C++语言使用递归求值波兰表达式

首先，需要了解波兰表达式的计算规则：从左到右扫描表达式，如果遇到操作数，则压入栈中；如果遇到运算符，则取出栈顶的两个操作数进行运算，并将结果压入栈中。最终，栈中只剩下一个元素，即为表达式的计算结果。

递归求值波兰表达式的思路是：如果当前字符为操作数，则直接返回该操作数；如果当前字符为运算符，则递归计算其两个操作数的值，并根据运算符进行相应的计算。

下面是用 C++语言实现递归求值波兰表达式的代码：

#include <iostream>
#include <stack>
#include <cstring>
#include <cstdlib>

using namespace std;

int evalRPN(string tokens) {
    stack<int> s;
    int n = tokens.length();
    if (n == 0)
        return 0;
    if (tokens[0] >= '0' && tokens[0] <= '9')
        return atoi(tokens.c_str());
    int right = evalRPN(tokens.substr(2));
    int left = evalRPN(tokens.substr(4 + to_string(right).length()));
    switch (tokens[0]) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
    }
    return 0;
}

int main() {
    string tokens = "+ 4 * 5 6";
    cout << evalRPN(tokens) << endl;
    return 0;
}

在这个例子中，我们使用了递归的方式来计算波兰表达式。在每次递归时，我们检查当前字符是操作符还是操作数。如果是操作数，则直接返回它的值。如果是操作符，则递归计算左右两个操作数的值，并根据操作符进行相应的计算。最终，递归回到最顶层时，栈中只剩下一个元素，即为表达式的计算结果。