856 Score of Parentheses

856. Score of Parentheses

1. Question

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

• ()has score 1

• ABhas scoreA + B, where A and B are balanced parentheses strings.

• (A)has score2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Note:

1. Sis a balanced parentheses string, containing only(and).

2. 2 <= S.length <= 50

2. Implementation

(1) Stack

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack();

        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(-1);
            }
            else {
                int score = 0;
                while (stack.peek() != -1) {
                    score += stack.pop();
                }
                stack.pop();
                // score不等于0时，说明有嵌套的括号出现，分数加倍
                stack.push(score == 0 ? 1 : 2 * score);
            }
        }

        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}

3. Time & Space Complexity

Stack: 时间复杂度: O(n), 空间复杂度: O(n)