2023-12-09 队列与栈二

栈与队列二

20. 有效的括号

核心：栈的基础用法了！注意使用栈的一些简洁方法就可以了

class Solution:
    def isValid1(self, s: str) -> bool:
        stack = []
        for v in s:
            if v == '(' or v == '{' or v == '[':
                stack.append(v)
            else:
                if not stack:
                    return False
                if v == ')' and stack[-1] == '(':
                    stack.pop()
                elif v == '}' and stack[-1] == '{' :
                    stack.pop()
                elif v == ']' and stack[-1] == '[':
                    stack.pop()
                else:
                    return False
        return not stack
    def isValid(self, s: str) -> bool:
        # 这种简洁一点写法
        stack = []
        for v  in s:
            if v == '(':
                stack.append(')')
            elif v == '[':
                stack.append("]")
            elif v == '{':
                stack.append("}")
            elif not stack or stack[-1] != v:
                return False
            else:
                # 相等弹出元素
                stack.pop()
        return True if not stack else False

1047. 删除字符串中的所有相邻重复项

思路：建立一个列表维护即可！也可以看成栈！

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = []
        for value in s:
            if res and value == res[-1]:
                res.pop()
                continue
            else:
                res.append(value)
        return "".join(res)

150. 逆波兰表达式求值

核心：是用栈的常见的应用！了解简洁的写法以及运行的思想即可！

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        # 
        stack = []
        for v in tokens:
            if v == '+':
                temp_1 = int(stack.pop())
                temp_2 = int(stack.pop())
                stack.append(temp_1 + temp_2)
            elif v == '-':
                temp_1 = int(stack.pop())
                temp_2 = int(stack.pop())
                stack.append(temp_2 - temp_1)
            elif v == '*':
                temp_1 = int(stack.pop())
                temp_2 = int(stack.pop())
                stack.append(temp_1 * temp_2)
            elif v == '/':
                temp_1 = int(stack.pop())
                temp_2 = int(stack.pop())
                stack.append(temp_2 / temp_1)
            else:
                stack.append(v)
        return int(stack.pop())
class Solution:
    '''
    Push the operands to a stack.
    When reached an operator, 
        pop two operands from the stack, 
        perform the operation, 
        and push the result back to the stack.
    Time complexity: O(n). Space complexity: O(n).
    '''
    def evalRPN(self, tokens: List[str]) -> int:
        s = []
        for token in tokens:
            if token in '+-*/':
                op1, op2 = s.pop(), s.pop()
                if token == '+':
                    s.append(op2 + op1)
                elif token == '-':
                    s.append(op2 - op1)
                elif token == '*':
                    s.append(op2 * op1)
                else:
                    s.append(int(op2 / op1)) # truncate towards zero
            else:
                s.append(int(token))
        return s[0]