10-28LeetCode刷题（四）

class Solution:
    def isValid(self, s:str) -> bool:
        maches = {'(':')', '[':']', '{':'}', '?':'?'}
        stack = ["?"]
        for i in s:
            if i in maches:
                stack.append(i)
            elif i != maches[stack.pop()]:
                return False
        return len(stack) == 1

class MinStack:

    def __init__(self):
        self.stack = []  #用来储存栈的元素
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

class Solution:

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token[-1].isdigit():
                stack.append(int(token))
            else:
                num2 = stack.pop() # 注意先弹出的应该是后面的操作数，栈是先进后出的
                num1 = stack.pop()
                stack.append(self.evaluate(num1,num2,token))
        return stack[0]

    def evaluate(self, num1, num2 ,op):
        if op == "+":
            return num1 + num2
        elif op == "*":
            return num1 * num2
        elif op == "-":
            return num1 - num2
        elif op == "/":
            return int(num1/num2)