当前位置： 面试刷题>> 逆波兰表达式求值(经典算法150题)
### 题目描述
逆波兰表达式（Reverse Polish Notation, RPN），也被称为后缀表达式，是一种不需要括号来标识运算符优先级的数学表示法。在这种表示法中，所有操作数都位于运算符之前。例如，表达式 `(3 + 4) * 2` 在逆波兰表示法中为 `3 4 + 2 *`。
**题目要求**：
实现一个函数来计算逆波兰表达式的值。函数接收一个字符串数组作为参数，其中每个元素是一个数字或运算符（`+`, `-`, `*`, `/`）。假设除法运算的结果总是整数，并且除法运算中的除数不为零。
### 示例
输入: `["2", "1", "+", "3", "*"]`
输出: 9
解释: ((2 + 1) * 3) = 9
### PHP 示例代码
```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 示例代码
```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 示例代码
```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 中实现逆波兰表达式的求值。这些代码都遵循了相同的逻辑：遍历表达式中的每个元素，将数字推入栈中，遇到运算符则从栈中弹出两个操作数，执行运算后再将结果推回栈中，最后栈中剩下的元素即为表达式的值。