难度: Medium
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。(A) 得 2 * A 分，其中 A 是平衡括号字符串。示例 1：
输入： "()" 输出： 1
示例 2：
输入： "(())" 输出： 2
示例 3：
输入： "()()" 输出： 2
示例 4：
输入： "(()(()))" 输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。2 <= S.length <= 50运行时间: 23 ms
内存: 16.0 MB
class Solution:
def scoreOfParentheses(self, s: str) -> int:
stack = []
for c in s:
if c == '(':
stack.append(c)
else:
cur = 0
while len(stack) > 0 and stack[-1] != '(':
cur += stack.pop()
stack.pop()
if cur == 0:
stack.append(1)
else:
stack.append(cur * 2)
return sum(stack)
该题解采用了栈的数据结构来分析和计算括号字符串的分数。对于遇到的每个'('，直接将其压入栈中；对于每个')'，首先尝试弹出栈顶元素直到遇到'('，累加这些元素的值作为当前括号内部的分数（如果栈顶是'('，则内部分数为0）。之后，将'('弹出栈，并根据内部的分数来决定将1（如果内部分数为0）还是2倍内部分数（如果内部分数不为0）压入栈中。最后，栈中剩余的数值为不同部分的分数，将这些数值累加即得到最终的分数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def scoreOfParentheses(self, s: str) -> int:
stack = [] # 初始化一个栈
for c in s: # 遍历输入字符串
if c == '(': # 如果字符是'('，将其压入栈
stack.append(c)
else: # 如果字符是')'
cur = 0 # 初始化当前内部分数
while len(stack) > 0 and stack[-1] != '(': # 弹出所有数值元素直到遇到'('
cur += stack.pop()
stack.pop() # 弹出'('
if cur == 0: # 如果内部分数为0，说明是空的括号对'()'
stack.append(1) # 分数为1
else: # 否则，括号内有内容
stack.append(cur * 2) # 分数翻倍
return sum(stack) # 返回栈中所有分数的总和
栈是处理括号匹配和嵌套问题的理想数据结构，因为它遵循后进先出的原则，可以有效地跟踪最近未匹配的括号。当解析到闭合括号时，栈可以帮助快速找到与之匹配的开括号，并处理中间的分数计算。反之，队列为先进先出，不便于回溯到最近的未匹配开括号。虽然递归也可以处理这类问题，但使用栈可以避免递归带来的额外内存消耗和复杂度，尤其是在处理大规模数据时更为高效。
在多层嵌套括号的情况下，当遇到闭合括号')'时，栈中的元素将被逐一弹出直到遇到匹配的开括号'('。这些被弹出的元素代表了括号内部可能的分数累积，例如由更深层嵌套的括号对生成的分数。一旦到达开括号，通过将这些分数累加（如果有的话）并乘以2（除非内部分数为0，此时结果为1），就可以正确计算出当前括号层的分数，然后将计算结果重新压入栈中，以便用于更高层的分数计算。这种方式确保了每一层的括号都可以正确计算其内部分数。
对于连续的平行括号如'()()'，每对括号独立计算分数后，结果会依次压入栈中。具体来说，对于每个'()'，由于内部没有其他元素，其分数为1。处理完第一对括号后，栈顶为1。处理第二对括号时同样结果为1。最后，栈中含有两个1，栈中所有元素的总和即为最终分数，对于'()()'来说，总分为2。这说明在处理连续平行括号时，每对括号的分数独立计算，然后累加即可得到总分数。