20. 有效的括号

link

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true

思路

使用栈来进行存储，遇到匹配的则出栈。

class Solution:
    def match(self, i, j):
        if i == "]" and j == "[":
            return True
        elif i == '}' and  j == '{':
            return True
        elif i == ')' and j == '(':
            return True
        else:
            return False


    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if len(stack) != 0:
                if self.match(i, stack[-1]):
                    stack.pop()
                else:
                    stack.append(i)
            else:
                stack.append(i)
        
        if len(stack) == 0:
            return True
        else:
            return False

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

link

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

思路

类似于上一题。可以理解为“消消乐”，遇到相同的则出栈。

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

150. 逆波兰表达式求值

link

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、’-‘、’*’ 和 ‘/‘ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是向零截断。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位整数表示。

思路

核心规则：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

注意题目中要求是向零截断，使用 // 不行。// 是向下取整，对于复数结果不满足向零截断（-1 // 2 == -1）。可以使用 int(a / b)。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens:
            if i.isdigit() or i.replace('-', '').isdigit():
                stack.append(int(i))
            else:
                num2 = stack.pop()
                num1 = stack.pop()
                if i == '-':
                    res = num1 - num2
                elif i == '+':
                    res = num1 + num2
                elif i == '*':
                    res = num1 * num2
                elif i == '/':
                    res = int(num1 / num2)

                stack.append(res)
        
        return stack[0]