856. Score of Parentheses

Problem

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:

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

Problem Summary

Calculate the score of parentheses according to the following rules: () represents 1 point. AB represents A + B, where A and B are both parenthesis groups that already satisfy the matching rules. (A) represents 2 * A, where A is also a parenthesis group that already satisfies the matching rules. Given a parentheses string, calculate the score value of the parentheses according to these rules.

Solution Approach

According to the principle of parentheses matching, calculate the score of each combination step by step and push it onto the stack. When encountering the 3 cases in the problem, take out the top element of the stack to calculate the score.

Code

package leetcode

func scoreOfParentheses(S string) int {
	res, stack, top, temp := 0, []int{}, -1, 0
	for _, s := range S {
		if s == '(' {
			stack = append(stack, -1)
			top++
		} else {
			temp = 0
			for stack[top] != -1 {
				temp += stack[top]
				stack = stack[:len(stack)-1]
				top--
			}
			stack = stack[:len(stack)-1]
			top--
			if temp == 0 {
				stack = append(stack, 1)
				top++
			} else {
				stack = append(stack, temp*2)
				top++
			}
		}
	}
	for len(stack) != 0 {
		res += stack[top]
		stack = stack[:len(stack)-1]
		top--
	}
	return res
}