括号的分数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

提示：

S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50

# 思路

栈思想，但没有用到栈。给定一个标记n，若‘(’则n左移，若‘)’则n右移，若遇到()则sum+=n

# 解法


class Solution {
    // 栈思想，但没有用到栈。给定一个标记n，若‘(’则n左移，若‘)’则n右移，若遇到()则sum+=n


    public int scoreOfParentheses(String S) {

        int length=S.length();
        int sum=0;
        int n=0;
        for(int i=0;i<length;i++)
        {
            if(S.charAt(i)=='(')
            {
                if(n==0)
                {
                    n=1;
                }
                else
                {
                    n=n<<1;
                }
            }
            else if(S.charAt(i)==')')
            {
                 if(S.charAt(i-1)=='(')
                {
                     sum+=n;
                }
                n=n>>1;
                
            }
        }
        return sum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 总结

分析出几种情况，然后分别对各个情况实现