[LeetCode Weekly Contest 90]856.括号的分数
原创
[LeetCode Weekly Contest 90]856.括号的分数
原创
杜逸先
发布于 2018-06-26 11:11:56
发布于 2018-06-26 11:11:56
题目描述
856.括号的分数
给定一个平衡括号字符串 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压栈，
- 遇到左括号压栈，
- 遇到右括号，弹出栈顶元素并累加，直到弹出左括号，将累加的和乘以2压栈
最后的结果就是所有栈内元素的和，例如处理‘1(1(11))’，也就是'()(()(()()))':
- 遇到
1,压栈，[1] - 遇到
(，压栈，[1, (] - 遇到
1，压栈，[1, (, 1] - 遇到
(，压栈，[1, (, 1, (] - 遇到两个
1， 先后压栈，[1, (, 1, (, 1, 1] - 遇到
)，弹出栈顶元素，在弹出(之前遇到两个1，求和得2，再乘以2压栈，[1, (, 1, 4,] - 遇到)，弹出栈顶元素，在弹出(之前遇到1和4，求和得5，再乘以2压栈，
[1, 10] - 扫描结束，结果就是栈内所有元素的和，为11
代码实现
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 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
