20.有效括号
20. 有效的括号 - 力扣（LeetCode）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
- 示例 1：
- 输入：s = "()"
- 输出：true
- 示例 2：
- 输入：s = "()[]{}"
- 输出：true
- 示例 3：
- 输入：s = "(]"
- 输出：false
解题思路
遍历字符串，栈为空append->continue，判断当前元素是否与前一元素相同，若一样pop，否则append
class Solution():
def isVaild(self,s):
stack = []
for i in s:
if i == "(":
stack.append(")")
elif i == "{":
stack.append("}")
elif i == "[":
stack.append("]")
elif stack and stack[-1]==i:
stack.pop()
else:
return False
return not stack
107.删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
- 示例：
- 输入："abbaca"
- 输出："ca"
- 解释：在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
解题思路
遍历s，若stack为空append->continue，若stack[-1]==i，pop，否则append```
class Solution():
def removeDuplicates(s):
stack = []
for i in s:
if stack==[]:
stack.append(i)
continue
if stack[-1]==i:
stack.pop()
else:
stack.append(i)
return "".join(stack)
150.逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣（LeetCode）
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
- 示例 1：
- 输入：tokens = ["2","1","+","3","*"]
- 输出：9
- 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
- 示例 2：
- 输入：tokens = ["4","13","5","/","+"]
- 输出：6
- 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
- 示例 3：
- 输入：tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
- 输出：22
- 解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
解题思路：
设置空栈，栈内元素少于两个append，遇到数字append（负数要注意！），遇到符号pop栈顶两位并计算，最后返回数值
class Solution():
def evalRPN(tokens):
stack = []
for i in tokens:
if len(stack)<3:
stack.append(i)
if i.isdigit() or (i[0]=='-' and i[1:].isdigit()):
stack.append(i)
elif i=="+":
second = stack.pop()
first = stack.pop()
stack.append(str(int(first)+int(second)))
elif i=="-":
second = stack.pop()
first = stack.pop()
stack.append(str(int(first)-int(second)))
elif i=="*":
second = stack.pop()
first = stack.pop()
stack.append(str(int(first)*int(second)))
elif i=="/":
second = stack.pop()
first = stack.pop()
stack.append(str(int(int(first)/int(second))))
else:
return False
return int(stack[0])