给定一个平衡括号字符串 S
,按下述规则计算该字符串的分数:
()
得 1 分。AB
得 A + B
分,其中 A 和 B 是平衡括号字符串。(A)
得 2 * A
分,其中 A 是平衡括号字符串。示例 1:
输入: "()"
输出: 1
示例 2:
输入: "(())"
输出: 2
示例 3:
输入: "()()"
输出: 2
示例 4:
输入: "(()(()))"
输出: 6
提示:
S
是平衡括号字符串,且只含有 (
和 )
。2 <= S.length <= 50
这个题目看起来有点像括号匹配的题目,但事实上是一个表达式求值。
不包含任何内容的括号()
得一分,事实上我们可以将()
替换为1
,这样题目就变成了1
得一分,并列的部分得分相加,括号内的部分得分乘以2,四个示例就转换为了:
示例 1:
输入: "1"
输出: 1
示例 2:
输入: "(1)"
输出: 2
示例 3:
输入: "11"
输出: 2
示例 4:
输入: "(1(1))"
输出: 6
我们可以像处理表达式求值一样,利用栈来存储:
最后的结果就是所有栈内元素的和,例如处理‘1(1(11))’,也就是'()(()(()()))':
1
,压栈,[1]
(
,压栈,[1, (]
1
,压栈,[1, (, 1]
(
,压栈,[1, (, 1, (]
1
, 先后压栈, [1, (, 1, (, 1, 1]
)
,弹出栈顶元素,在弹出(之前遇到两个1,求和得2,再乘以2压栈,[1, (, 1, 4,]
[1, 10]
class Solution:
def scoreOfParentheses(self, S):
"""
:type S: str
:rtype: int
"""
S = S.replace('()', '1')
stack = []
for ch in S:
if ch == '(':
stack.append(ch)
elif ch == '1':
stack.append(1)
else:
num = 0
while stack[-1] != '(':
num += stack.pop()
stack.pop()
stack.append(num * 2)
return sum(stack)
其实不讲()
替换为1
也可以,这样的话遇到)
的时候如果栈顶就是(
,弹出(
并压入1
就可以了。这在使用不能方便的进行字符串替换的语言中(C语言)是优先选择。
class Solution:
def scoreOfParentheses(self, S):
"""
:type S: str
:rtype: int
"""
stack = []
for ch in S:
if ch == '(':
stack.append(ch)
else:
num = 0
if stack[-1] == '(':
stack.pop()
stack.append(1)
else:
while stack[-1] != '(':
num += stack.pop()
stack.pop()
stack.append(num * 2)
return sum(stack)
今天的建议是善于把握问题的实质,不要被表象迷惑。
最后祝大家享受生活,享受代码。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。