From Leetcode 856 Score of Parentheses

1. Problem Description

Given a balanced parentheses string s, return the score of the string. The score of a balanced parentheses string is 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.

1.1 Solution

we use stack to solve this problem:

  • If there is a (, we add it to stack because it must match with a ) to get valid value back;
  • If there is a ), we can try to match it with the top value in stack:
  • we can either +1 or *2, here is a tricky way to tackle it: we always choose the greater one : (2 * last) or 1
def scoreOfParentheses(self, s: str) -> int:
# Create stack
stack = [0] 
for c in s:
if c == "(":
stack.append(0)
else:
last = stack.pop()
stack[-1] += (2 * last) or 1
print(stack)
return stack[-1]