Day 11 栈与队列：20. 有效括号，1047. 删除字符串相邻重复项, 150. 逆波兰表达式

20. 有效的括号

• 思路
  • example
    • '(([]{}))'
    • '(([]})'
    • '(('
  • 用list实现stack (FILO), 用dict记录配对。
  • 最后return的时候注意判断stack是否非空。
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if n % 2 == 1:
            return False
        pairs = {')': '(',
                 ']': '[',
                 '}': '{'}
        stack = list()
        for ch in s:
            if ch not in pairs:
                stack.append(ch)
            else:
                if not stack or stack[-1] != pairs[ch]:
                    return False  
                stack.pop()
        return not stack 

class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        mapping = {'(': ')', '[': ']', '{': '}'}
        stack = []
        for i in range(n):
            if s[i] in mapping:
                stack.append(s[i])
            else:
                if stack == [] or mapping[stack.pop()] != s[i]:
                    return False 
        if stack == []:
            return True 
        else:
            return False 

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {'(' : ')', '[': ']', '{': '}'}
        stack = []
        for ch in s:
            if ch in pairs:
                stack.append(ch) 
            else:
                if stack == []: # !!!
                    return False 
                else: 
                    ch0 = stack.pop()  
                    if pairs[ch0] != ch: # !!!
                        return False   
        if stack: # !!!
            return False  
        return True 

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

• 思路
  • example: "abbaca" --> "ca"
  • list: stack (FILO)
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = list()
        for ch in s:
            if not stack or stack[-1] != ch:
                stack.append(ch)
            else:
                stack.pop()
        return ''.join(stack) 

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for ch in s:
            if stack == [] or stack[-1] != ch:
                stack.append(ch) 
            else:
                stack.pop()
        return ''.join(stack)

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = [] 
        for ch in s:
            if stack == []:
                stack.append(ch) 
            else:
                if stack[-1] == ch:
                    stack.pop() 
                else:
                    stack.append(ch) 
        return ''.join(stack)  

150. 逆波兰表达式求值

• 思路
  • example
  • list: stack
  • 字符串与数字的转化。
    • str(int(num1 / num2))
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        opes = ['+', '-', '*', '/']
        for ch in tokens:
            if ch not in opes:
                stack.append(int(ch))
            else:
                num2 = stack.pop()
                num1 = stack.pop()
                if ch == '+':
                    stack.append(num1 + num2)
                elif ch == '*':
                    stack.append(num1 * num2) 
                elif ch == '-':
                    stack.append(num1 - num2)
                elif ch == '/':
                    # stack.append(num1 // num2) # 6 // (-132) = -1
                    stack.append(int(num1 / num2))
        return stack[0]

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        n = len(tokens)
        stack = []
        # opes = set('+', '-', '*', '/')
        opes = ['+', '-', '*', '/']
        for ch in tokens:
            if ch not in opes:
                stack.append(int(ch))
            else:
                second = stack.pop()
                first = stack.pop()
                if ch == '+':
                    stack.append(first + second)
                elif ch == '-':
                    stack.append(first - second)
                elif ch == '*':
                    stack.append(first * second)
                else:
                    # stack.append(first // second) 
                    stack.append(int(first / second))
        return stack[0] 

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        set1 = {'+', '-', '*', '/'} 
        stack = [] 
        for ch in tokens:
            if ch not in set1:
                stack.append(int(ch)) 
            else:
                num2 = stack.pop() 
                num1 = stack.pop() 
                if ch == '+':
                    stack.append(num1+num2) 
                elif ch == '-':
                    stack.append(num1-num2) 
                elif ch == '*':
                    stack.append(num1*num2) 
                else:
                    stack.append(int(num1/num2))
        return stack[-1]