day11| 20.有效的括号；150.逆波兰表达式求值；1047.删除字符串中的所有相邻重复项

20. 有效的括号

题目简述：

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

有效字符串需满足：

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

思路：

1. 利用一个栈实现

2. 构建一个字典，键为右括号，值为左括号

3. 当s的长度为奇数，直接返回false

4. 当ch字符为左括号，存入stack

5. 当ch字符为右括号，判断stack最后一个字符是否为对应的左括号。如果不是，返回False；如果是，删除之

6. 遍历结束，看看stack是否为空，为空则说明刚好都一一配对了，返回True

代码如下：

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

150. 逆波兰表达式求值

题目简述：

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

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

注意：

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

思路：

1. 遇到数字就进栈

2. 遇到操作符，就从栈顶弹出两个数字，用操作符处理这两个数字

代码如下：

class Solution(object):
    def evalRPN(self, tokens):
        stack = []
        for token in tokens:
            try:
                stack.append(int(token))
            except:
                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 / float(num2))

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

题目简述：

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

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

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

思路：

1. 构建一个栈

2. 遍历字符串

3. 看栈中的最后一个字符是不是当前遍历的字符

4. 不是，就放入栈中，是的话，就都删除

代码如下：

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

总结：

1. 栈的后进先出要牢记

2. 字典的运用还要多多练习

3. 可以经常使用[-1]取出栈中倒数第一个值