current position:Home>[leetcode] Reverse Polish Expression

[leetcode] Reverse Polish Expression

2022-09-23 09:32:35Good procedure does not lose hair

堆栈,时间复杂度O(n),空间复杂度O(n)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c in ["+", "-", "*", "/"]: # Note(1)
                num_after = stack.pop() # Note(2)
                num_before = stack.pop() 
                if c == '+':
                    res = num_before + num_after
                elif c == '-':
                    res = num_before - num_after
                elif c == '/':
                    res = int(num_before / num_after) # Note(3)
                elif c == '*':
                    res = num_before * num_after
                stack.append(res)       
            else:
                # c是数字
                stack.append(int(c))
               
        return stack[0]

Ideas use stacks,There are three pits and details,Avoid everyone stepping on it

Note(1) numbers will be greater than10,不能用 ‘0’ <= c <= '9’判断是否是数字
Note(2) The number after the operator is popped off the top of the stack firstnum2,What pops out is the number in front of the operatornum1, The order is right
Note(3) pythonThe division of is inconsistent with the division in the title description,需要int取整
最后的大boss:python只维护到2020年,进化后的python3不向下兼容,The previous topic is inpythoncompiled in the compiler,We will use it laterpython3的吧~哈哈哈哈

copyright notice
author[Good procedure does not lose hair],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/266/202209230929503653.html

Random recommended