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.

这道题一开始看leet code上的article没有特别懂，和朋友讨论了后思路如下，想和大家分享，附了python solution在最后，求大米~~

这道题是看到右括号就要开始计算，last in first out，所以这里我们用stack。问题是，我们什么时候值是1，什么时候算加法or乘法

step1: 看到左括号就push一个0进stack里，看到右括号就开始算。pop出来的是0的话，就是代表这个右括号前面是左括号，rule1，() = 0。
step2: 每次计算之后，都把结果存在上一层的括号里，这也是符合rule2的。这样的话，pop时候的元素，就是这个括号里面的值。
step3： 如果等于0, 就是空括号，rule1。如果大于0，就用rule3计算把里面的值*2 。

一开始stack中有个0，我的理解就是我们最后要的结果就是相当于在原来的式子外面套一层括号，原来的式子的结果存在我们加的这个括号里。

python solution

1. def parentheses_score(parestr):
   
2.     """Evaluate the score of a balanced parebtheses string.
   
3. 
   
4.     () has score 1
   
5.     AB has score A + B, where A and B are balanced parentheses strings.
   
6.     (A) has score 2 * A, where A is a balanced parentheses string.
   
7.     """
   
8.     stack = [0]
   
9.     for i in parestr:
   
10.         if i == "(":
    
11.             stack.append(0)
    
12.         else:
    
13.             top = stack.pop()
    
14.             if top == 0:
    
15.                 stack[-1] += 1
    
16.             else:
    
17.                 stack[-1] += top * 2
    
18.     return stack[0]
    
19. 
    
20. # time O(n)
    
21. # space O(n)
    

复制代码