题目描述

逆波兰表达式（Reverse Polish Notation, RPN），也被称为后缀表达式，是一种不需要括号来标识运算符优先级的数学表示法。在这种表示法中，所有操作数都位于运算符之前。例如，表达式 (3 + 4) * 2 在逆波兰表示法中为 3 4 + 2 *。

题目要求： 实现一个函数来计算逆波兰表达式的值。函数接收一个字符串数组作为参数，其中每个元素是一个数字或运算符（+, -, *, /）。假设除法运算的结果总是整数，并且除法运算中的除数不为零。

示例

输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: ((2 + 1) * 3) = 9

PHP 示例代码

function evalRPN($tokens) {
    $stack = [];
    foreach ($tokens as $token) {
        if (is_numeric($token)) {
            $stack[] = intval($token);
        } else {
            $operand2 = array_pop($stack);
            $operand1 = array_pop($stack);
            switch ($token) {
                case '+':
                    $stack[] = $operand1 + $operand2;
                    break;
                case '-':
                    $stack[] = $operand1 - $operand2;
                    break;
                case '*':
                    $stack[] = $operand1 * $operand2;
                    break;
                case '/':
                    // 假设除法结果总是整数
                    $stack[] = intval($operand1 / $operand2);
                    break;
            }
        }
    }
    return $stack[0];
}

// 测试示例
$tokens = ["2", "1", "+", "3", "*"];
echo evalRPN($tokens);  // 输出 9

Python 示例代码

def evalRPN(tokens):
    stack = []
    for token in tokens:
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                stack.append(operand1 + operand2)
            elif token == '-':
                stack.append(operand1 - operand2)
            elif token == '*':
                stack.append(operand1 * operand2)
            elif token == '/':
                # 假设除法结果总是整数
                stack.append(int(operand1 / operand2))
    return stack[0]

# 测试示例
tokens = ["2", "1", "+", "3", "*"]
print(evalRPN(tokens))  # 输出 9

JavaScript 示例代码

function evalRPN(tokens) {
    const stack = [];
    tokens.forEach(token => {
        if (!isNaN(token)) {
            stack.push(parseInt(token));
        } else {
            const operand2 = stack.pop();
            const operand1 = stack.pop();
            switch (token) {
                case '+':
                    stack.push(operand1 + operand2);
                    break;
                case '-':
                    stack.push(operand1 - operand2);
                    break;
                case '*':
                    stack.push(operand1 * operand2);
                    break;
                case '/':
                    // 假设除法结果总是整数
                    stack.push(Math.trunc(operand1 / operand2));
                    break;
            }
        }
    });
    return stack[0];
}

// 测试示例
const tokens = ["2", "1", "+", "3", "*"];
console.log(evalRPN(tokens));  // 输出 9

以上代码示例展示了如何在 PHP、Python 和 JavaScript 中实现逆波兰表达式的求值。这些代码都遵循了相同的逻辑：遍历表达式中的每个元素，将数字推入栈中，遇到运算符则从栈中弹出两个操作数，执行运算后再将结果推回栈中，最后栈中剩下的元素即为表达式的值。