Score of Parentheses

LeetCode Q 856 - Score of Parentheses

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

• () has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * 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:

• S is a balanced parentheses string, containing only ( and ).
• 2 <= S.length <= 50

Solution

Code

public int scoreOfParentheses(String S) {

  int totalScore = 0;

  Deque<Integer> stack = new ArrayDeque<>();

  for (char ch: S.toCharArray()) {
    if (ch == '(') {
      stack.push(-1);
    } else {
      int curScore = 0;
      while (!stack.isEmpty() && stack.peek() != -1)
        curScore += stack.pop();

      stack.pop(); // pop the ( matching the current )
      curScore = curScore == 0 ? 1 : 2 * curScore;
      stack.push(curScore);
    }
  }

  for(int score: stack) totalScore += score;

  return totalScore;
}