本文共 2107 字，大约阅读时间需要 7 分钟。

题目：

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

解释：

class Solution(object):    def scoreOfParentheses(self, S):        """        :type S: str        :rtype: int        """        stack=[]        for s in S :            if s=='(':                stack.append(s)            else:                pre=stack.pop()                if pre=="(":                    stack.append(1)                else:                    current_sum=pre                    while stack[-1]!='(':                        current_sum+=stack.pop()                    stack.pop()                    stack.append(current_sum*2)        return sum(stack)

python的list没有变量类型的限制，可以随便放数字或者 char，但是c++的stack要设置类型的，怎么办？只能把(用数字0来表示。

#include
   
    using namespace std;class Solution {
   public:    int scoreOfParentheses(string S) {
           stack
    
      _stack;        for (auto s:S)        {
                 if (s=='(')                _stack.push(0);            else            {
                   int pre=_stack.top();                _stack.pop();                if (pre==0)                    _stack.push(1);                else                {
                       int cur_sum=pre;                    while(_stack.top()!=0)                    {
                           cur_sum+=_stack.top();                        _stack.pop();                    }                    _stack.pop();                    _stack.push(2*cur_sum);                }            }            }        int result=0;            while(!_stack.empty())            {
                   result+=_stack.top();                _stack.pop();            }            return result;    }};
    
   

解释：

转载地址：http://zwmcn.baihongyu.com/