# 0150. 逆波兰表达式求值

### 题目地址(150. 逆波兰表达式求值)

<https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/>

### 题目描述

```
根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

 

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

```

### 前置知识

* 栈

### 公司

* 阿里
* 腾讯

### 思路

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为`中缀表示`。

波兰逻辑学家 J.Lukasiewicz 于 1929 年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为`后缀表示`。

> 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为 ab+cd+*

思路就是：

* 遍历列表，依次入栈，直到遇到算数运算符。
* 将栈顶两个元素出栈运算，将结果压栈
* 重复以上过程直到所有的 token 都处理完毕。

![](https://p.ipic.vip/jkki9k.jpg)

### 关键点

1. 栈的基本用法
2. 如果你用的是 JS 的话，需要注意/ 和 其他很多语言是不一样的
3. 如果你用的是 JS 的话，需要先将字符串转化为数字。否则有很多意想不到的结果
4. 操作符的顺序应该是 先出栈的是第二位，后出栈的是第一位。 这在不符合交换律的操作中很重要， 比如减法和除法。

### 代码

代码支持：JS，Python，Java, CPP

JS Code:

```js
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  // 这种算法的前提是 tokens是有效的，
  // 当然这由算法来保证
  const stack = [];

  for (let index = 0; index < tokens.length; index++) {
    const token = tokens[index];
    // 对于运算数， 我们直接入栈
    if (!Number.isNaN(Number(token))) {
      stack.push(token);
    } else {
      // 遇到操作符，我们直接大胆运算，不用考虑算术优先级
      // 然后将运算结果入栈即可

      // 当然如果题目进一步扩展，允许使用单目等其他运算符，我们的算法需要做微小的调整
      const a = Number(stack.pop());
      const b = Number(stack.pop());
      if (token === "*") {
        stack.push(b * a);
      } else if (token === "/") {
        stack.push((b / a) >> 0);
      } else if (token === "+") {
        stack.push(b + a);
      } else if (token === "-") {
        stack.push(b - a);
      }
    }
  }

  return stack.pop();
};
```

Python Code:

```python
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        if len(tokens) > 2:
            stack = []
            operations = ['+', '-', '*', '/']
            for token in tokens:
                if token in operations:
                    b = int(stack.pop())
                    a = int(stack.pop())
                    if '+' == token:
                        tmp = a + b
                    elif '-' == token:
                        tmp = a - b
                    elif '*' == token:
                        tmp = a * b
                    else:
                        tmp = int(a / b)
                    stack.append(tmp)
                else:
                    stack.append(token)
            return stack[0]
        return int(tokens[-1])
```

Java Code:

```java
class Solution {
    public static int evalRPN(String[] tokens) {
	int[] numStack = new int[tokens.length / 2 + 1];
	int index = 0;
	for (String s : tokens) {
	    if (s.equals("+")) {
                numStack[index - 2] += numStack[--index];
            } else if (s.equals("-")) {
                numStack[index - 2] -= numStack[--index];
            } else if (s.equals("*")) {
                numStack[index - 2] *= numStack[--index];
            } else if (s.equals("/")) {
                numStack[index - 2] /= numStack[--index];
            } else {
                numStack[index++] = Integer.parseInt(s);
            }
	}
	return numStack[0];
    }
}
```

CPP Code:

```cpp
	class Solution {
public:
  int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for (string t : tokens) {
      if (isdigit(t.back())) s.push(stoi(t));
      else {
        int n = s.top();
        s.pop();
        switch(t[0]) {
          case '+': s.top() += n; break;
          case '-': s.top() -= n; break;
          case '*': s.top() *= n; break;
          case '/': s.top() /= n; break;
        }
      }
    }
    return s.top();
  }
};
```

### 扩展

逆波兰表达式中只改变运算符的顺序，并不会改变操作数的相对顺序，这是一个重要的性质。另外逆波兰表达式完全不关心操作符的优先级，这在中缀表达式中是做不到的，这很有趣，感兴趣的可以私下查找资料研究下为什么会这样。

```
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/150.evaluate-reverse-polish-notation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.