代码随想录算法训练营第十一天| 20. 有效的括号、1047.删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

代码随想录算法训练营第十一天| 20. 有效的括号、1047.删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

题目

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        return True if not stack else False

题目

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

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

题目

150.逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op_map = {'+': lambda x, y: int(x+y), '-': lambda x, y: int(x-y), '*': lambda x, y: int(x*y), '/': lambda x, y: int(x/y)}
        stack = []
        operater = ['+', '-', '*', '/']
        for token in tokens:
            # 说明是数字
            if token not in operater:
                stack.append(int(token))
            # 遇到运算符了
            else:
                b = stack.pop()
                a = stack.pop()
                c = op_map[token](a, b)
                stack.append(c)
        return stack.pop()