20. 有效的括号

题目链接：

20. 有效的括号 - 力扣（Leetcode）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

收获的点：

1）明确思路很重要，每遇到一个左括号，在栈里面添加一个匹配的右括号，当右括号出现，判断是否和栈顶的括号一致，如果不一致返回false，如果一致就把栈最外面的元素去掉，循环结束后，如果栈是空的话，那就说明括号完全匹配，是有效的。
2）python的pop()函数默认是删除列表中的最后一个元素

完整代码：

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. 删除字符串中的所有相邻重复项

题目链接：

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

思路：

通过遍历字符串中的所有元素，如果与前一个元素不相等，在栈里面添加该元素，如果遍历的元素和栈顶的元素相等，则把栈顶去掉，实现删除重复元素的操作
''.join(list) 返回列表的字符串形式

完整代码：

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for item in s:
            if stack and item == stack[-1]:
                stack.pop() #默认删除列表的最后一个元素
            else:
                stack.append(item)

        return ''.join(stack)

双指针解法：
快指针遍历元素，慢指针删除重复元素，通过调整slow位置，stack[slow]= stack[fast]重新赋值，

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = list(s)
        slow,fast = 0,0
        length = len(s)
        while fast < length:
            stack[slow] = stack[fast]
            if slow>0 and stack[slow] == stack[slow-1]:
                slow -=1
            else:
                slow +=1
            fast +=1
        return ''.join(stack[0:slow])

150. 逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（Leetcode）
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
**注意 **两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

收获的点：

确实题目不难，看完讲解能够自己写出代码。有个点需要注意：
1）注意第二个出来的数在运算符左边；没注意到踩坑了；
2）python的整数除法是向下取整，不是向零取整
python3 的地板除 "//" 是整数除法， "-3 // 2 = -2" ；
python3 的除法 "/" 是浮点除法， "-3 / 2 = -1.5" ；
对 Python 的整数除法问题，可以用 int(num1 / float(num2)) 来做，即先用浮点数除法，然后取整。
无论如何，浮点数除法都会得到一个浮点数，比如 "-3 / 2.0 = 1.5" ；
此时再取整，就会得到整数部分，即 float(-1.5) = -1 。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for item in tokens:
            if item in {'-','/','*','+'}:
                a = stack.pop()
                b = stack.pop()
                if item == '-':
                    c = b-a
                elif item == '/':
                    c = int(b/float(a)) # Python 的整数除法问题，可以用 int(num1 / float(num2)) 来做，即先用浮点数除法，然后取整；python中的整数除法是向下取整不是向零取整
                elif item == '*':
                    c = b*a
                else:
                    c = b+a 
                stack.append(c)
            else:
                stack.append(int(item))
        return int(stack.pop())  

eval 函数对字符串进行计算

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for item in tokens:
            if item not in {'+','-','*','/'}:
                stack.append(int(item))
            else:
                a,b = stack.pop(),stack.pop()
                c = int(eval(f'{b}{item}{a}'))
                stack.append(c)
        return int(stack.pop())