20. 有效的括号

如果当前是左括号，则入栈
如果当前是右括号，且栈不为空、栈顶是与其匹配的左括号，则出栈

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic={'(':')','{':'}','[':']'}
        stack=[]
        for c in s:
            if c in dic:
                stack.append(c)
            elif stack and c==dic[stack[-1]]:
                stack.pop()
            else:
                return False # 和栈顶的左括号不匹配
        return len(stack)==0

921. 使括号有效的最少添加

统计不可匹配的括号数 = 使括号有效的最少添加

加一个’?’打底，防止栈为空并且需要pop时报错
若栈顶为左括号，且当前元素为右括号，可以互相抵消。此时栈顶出栈
其他情况：抵消不了. 此时，不管是左括号还是右括号, 通通入栈

class Solution(object):
    def minAddToMakeValid(self, S):
        stack=['?'] # 加一个'?'打底，防止栈为空并且需要pop时报错
        for i in S:
            if stack[-1]=='(' and i==')':# 栈顶为左括号，且当前元素为右括号，可以互相抵消。此时栈顶出栈
                stack.pop()
            else: # 抵消不了的元素通通入栈
                stack.append(i)
        return len(stack)-1

1541. 平衡括号字符串的最少插入次数

将双括号替换为]
如果是左括号，则入栈
如果是右括号，则根据是否有左括号与之匹配，更新相关的细节

class Solution(object):
    def minInsertions(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=["?"] # 用一个字符打底，防止栈为空。这是一种常用的操作
        s=s.replace("))","]") #替换后，直接变成了三种类型的判断
        count=0 # 统计遍历过程中需要修改的步骤
        for i in s:
            if i=="(": # 左括号，入栈
                stack.append(i)
            elif i=="]": # 双右括号类型
                if stack[-1]=="(": # 匹配，可抵消。栈顶出栈
                    stack.pop()
                elif stack[-1]=="?": # 没有左括号与之匹配，需要增加1个左括号
                    count+=1
            elif i==")": # 单右括号类型
                if stack[-1]=="(": # 有左括号与当前的单右括号匹配，但需增加一个右括号。然后栈顶出栈
                    count+=1
                    stack.pop()
                elif stack[-1]=="?": # 没有左括号与当前的单右括号匹配，需增加一个左括号和一个右括号
                    count+=2
        return count+(len(stack)-1)*2   # 其中，len(stack)-1为抵消后剩下的左括号数量，需要双倍的右括号

1249. 移除无效的括号

(入栈
)
- 有(与之抵消，出栈
- 否则当前字符用空字符代替
无法抵消的(也用空字符代替

class Solution(object):
    def minRemoveToMakeValid(self, s):
        """
        :type s: str
        :rtype: str
        """
        n=len(s)
        s=list(s) # 临时转为list
        stack=[]
        for i in range(n):
            if s[i]=="(": # 只有左括号，才入栈
                stack.append(i)
            elif s[i]==")":
                if stack: # 当前是右括号且栈不为空（栈中有左括号，因此可抵消），出栈
                    stack.pop()
                else:
                    s[i]="" # 无法与当前右括号抵消，当前字符用空字符代替
        for i in stack: # 无法抵消的左括号也用空字符代替
            s[i]=""
        return "".join(s) # 列表转字符串，并消除空字符

856. 括号的分数

当前为左括号，入栈
当前为右括号，栈顶为左括号，可抵消。左括号出栈，记1分
当前为右括号，栈顶为数字，则不断累积和，直到遇到之前的左括号，左括号出栈。把累积和乘以2，入栈
最后结果中保存的只有数字，把数字加起来，就是结果

class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[]
        for i in range(len(s)):
            if s[i]=="(": # 左括号，入栈
                stack.append(s[i])
            elif s[i]==")" and stack[-1]=="(": # 当前是右括号，并且能和栈顶的左括号抵消
                stack.pop() # 弹出栈顶左括号
                stack.append(1) # 记1分
            elif s[i]==")" and str(stack[-1]).isdigit(): # 当前是右括号，栈顶是数字
                tmp=0
                while str(stack[-1]).isdigit(): # 把数字加起来
                    tmp+=stack.pop()
                stack.pop() # 弹出左括号
                stack.append(tmp*2)

        return sum(stack) # 栈中此时保存的是类似于[2,3]的信息，累积和即为结果

其他写法：

用栈记录字符串 s 对应的分数。初始栈顶部的分数为0。
遍历字符串：
若 s[i] == ‘(‘，先将分数0压入栈顶占位
若 s[i] == ‘)’，此时有两种情况：
s[i - 1] == ‘(‘，这是一个 ‘()’，此时栈顶值 v 为0，该分数为1
s[i - 1] != ‘(‘，这是一个外层括号，该分数为栈顶值 v × 2

题目思路

class Solution(object):
    def scoreOfParentheses(self, S):
        stack = [0] # 保存并不断更新结果
        for par in S:
            if par == "(": stack.append(0)
            else:
                last = stack.pop()
                if last == 0: score = 1
                else: score = last * 2
                stack[-1] += score
        return stack[0]