Evaluate Reverse Polish Notation
你会得到一个用逆波兰表示法表示的算术表达式，它是一个由词元组成的数组。每个运算符都紧跟在它的两个操作数之后，因此 3 4 + 表示 3 + 4，而 3 4 + 2 * 表示 (3 + 4) * 2，不需要括号。每个词元都是一个整数，或者是运算符 +、-、* 和 / 之一。
返回表达式的值。除法向零截断：7 / 2 的结果是 3，而 -7 / 2 的结果是 -3。
函数
- tokensstring-array
- 该表达式中的数字和运算符，按顺序排列
- 返回值integer
- 表达式的值
约束条件
1 ≤ tokens.length ≤ 104- 每个标记都是
+、-、*、/，或用十进制表示的整数，范围为-200到200，负数前面带负号。 tokens是一个有效的逆波兰表达式。- 不会发生除以零的情况，并且每个中间值和最终值都大于
-231且小于231。
示例
- 输入
- tokens = ["8", "3", "-", "4", "*"]
- 输出
- 20
- 解释
-先作用于 8，再作用于 3，按这个顺序计算，所以结果是 5，而不是 -5。然后，*将这个 5 乘以 4，结果是 20。
- 输入
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- 输出
- -6
- 解释
/使用最近的两个值：9 除以 3 等于 3。然后，-计算 2 减去 3，结果是 -1，*再将 6 乘以 -1。
- 输入
- tokens = ["10", "-7", "2", "/", "+"]
- 输出
- 7
- 解释
- 令牌
-7是一个数字，不是运算符。-7 除以 2 等于 -3.5，向零截断后得到 -3，而不是 -4；10 加上 -3 等于 7。
进阶
你能用普通记法重新写出这个表达式吗？例如 (3 + 4) * 2，只在会改变含义的地方加括号。
提示
逐个打开提示，每个都会多透露一点。
从左到右读取这些标记。遇到运算符时，它作用于哪两个值？看看这些值的生成顺序。
运算符总是作用于最近的两个尚未被运算符使用的值，其结果会成为后续运算符的新值。“最近的尚未使用的值”正是栈所提供的。
将每个数字压入栈中。遇到运算符时，先弹出右操作数，再弹出左操作数，按这个顺序将它们组合起来，并将结果压入栈中。处理完所有令牌后，栈中会剩下一个值：答案。确保除法的结果向零截断。
题解
每个运算符都作用于它前面的两个值，其中任意一个值都可能是前一个运算符的结果。因此，一串值会通过一次遍历计算出表达式的值。需要注意的陷阱包括 - 和 / 的操作数顺序、区分运算符 - 和数字 -7，以及截断除法。
折叠第一个运算符，重复
结果正确，但无法在最大的测试中运行完毕
思路
找到最左边的运算符。它前面没有其他运算符，因此它前面的两个词元是数字，也就是它的操作数。将这三个词元替换为运算结果。它后面的运算符会在原位置看到这个值，因此表达式的含义保持不变。重复此过程，直到只剩下一个数字。
每一轮都会从头开始搜索。5,000 个数字后面跟着 4,999 个运算符，第一个运算符在每一轮中都大约位于中间，因此仅搜索就会读取约 1.25 × 10^7 个词元。
算法
- 将这些标记复制到一个可修改的列表中。
- 从开头扫描，直到找到第一个运算符，位置为
k。 - 将它应用于位置
k-2（左侧）和k-1（右侧）的数字。 - 将位置
k-2、k-1和k处的三个标记替换为结果。 - 重复此过程，直到只剩下一个标记，然后将其作为数字返回。
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])使用值栈进行一次遍历
思路
把运算符左侧的值保存在栈中，而不是重新读取它们。数字会压入栈中。运算符会弹出两个值，将它们组合后再把结果压入栈中，等待下一个运算符处理，就像其他值一样。栈始终按顺序保存目前读到的完整部分的值，因此运算符总是作用于栈顶的两个值。栈顶的值是右操作数，因为它是最后生成的。
在 6 2 9 3 / - * 中，/ 先弹出 3，再弹出 9，然后压入 3；- 先弹出 3，再弹出 2，然后压入 -1；* 则压入 6 × -1 = -6。每个记号只处理一次：时间复杂度为 O(n)，空间复杂度为 O(n)。
算法
- 从一个空栈开始。
- 对于每个数字令牌，将它的值压入栈中。
- 对于每个运算符，先弹出右操作数，再弹出左操作数。
- 计算
left op right，对于/，结果向零截断，然后将结果压入栈中。 - 处理完最后一个令牌后，返回栈中的唯一值。
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
易错点和边界情况
- 交换操作数。第一次弹出的是右操作数：
["3", "5", "-"]的结果是 -2，而["2", "9", "/"]的结果是 0，不是 4。 - 不要只看运算符的第一个字符。
-7以减号开头，但它是一个数字，因此要比较整个标记。 - 不要向下取整，而要截断。Python 的
//、Ruby 的/、R 的%/%和 Lua 的math.floor会将-7 / 2变成 -4，将-1 / 3变成 -1。 - 不要输出
-0。在 JavaScript 和 Lua 中，0 * -5和Math.trunc(-1 / 3)会得到负零。给最终值加上 0。
常见问题4
计算逆波兰表示法的时间复杂度是多少？
对于 n 个令牌，栈解法的运行时间为 O(n)：每个数字入栈一次，每个运算符执行两次出栈和一次入栈。栈最多可存储约 n/2 个值，因此空间复杂度为 O(n)。
为什么逆波兰表示法不需要括号？
在普通记法中，3 + 4 * 2 需要优先级规则或括号来说明哪个运算先进行。在逆波兰记法中，运算符总是作用于它前面的两个值，因此由词元顺序决定结果：3 4 2 * + 的结果是 11，而 3 4 + 2 * 的结果是 14。
如何在 Python 中进行向零截断的除法？
使用 int(a / b)。// 运算符会向下取整，因此 -7 // 2 的结果是 -4，而 int(-7 / 2) 的结果是 -3。对于 32 位值，浮点除法的精度足够。对于更大的整数，使用 // 对绝对值进行除法，再加回符号。
如何将普通表达式转换为逆波兰表示法？
调度场算法通过一个运算符栈，一次遍历即可完成。数字直接放入输出中。压入运算符之前，先将栈中所有优先级更高或相同的运算符移到输出中。遇到右括号时，将运算符移出栈，直到遇到与之匹配的左括号。最后，将剩余运算符移到输出中。
def evalRPN(tokens):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tokens = ["8", "3", "-", "4", "*"]
预期输出
20