Score of Parentheses

原题链接

Given a balanced parentheses string S, compute the score of the string based on the following rule:

1. () has score 1
2. AB has score A + B, where A and B are balanced parentheses strings.
3. (A) has score 2 * A, where A is a balanced parentheses string.

Input: “()”
Output: 1

题意:形成一对括号是1分,括号内有括号表达式则分数乘2,并列的两个括号表达式分数直接相加

与括号生成相关的题目一般都会使用到栈,此题也不例外,因为如果括号内又有括号表达式,那么会乘2,所以可以考虑引入括号层数(深度)的概念。用栈维护每一层的分数,每遇到一个左括号,表示进入了新的一层,在一层的括号对形成后,上一层的分数就要累加该层分数*2,只需要注意单独处理单一的一对()(因为按照上面的思路,该层的下一层为空,分数为0,所以这一对()的分数会是0*2,而实际上应该是1)

代码如下:

发表评论

电子邮件地址不会被公开。