0%

LeetCode 856. Score of Parentheses

Posted on Edited on In

题目

原题在此

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

解析

用stack记录字符串,是'('就入栈一个0; 是')'时, 若栈顶为0, 则说明此时括号内还没有数字, 将栈顶元素修改为1; 若不是0,则说明括号内以有元素, 此时应乘二. 累加求和.
当然也可以直接用解释型语言, 替换字符串, 调用表达式.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> stk;
        stk.push(0);
        int tmp;
        for(char c : S) {
            if(c == '(') {
                stk.push(0);
            } else {
                tmp = stk.top();
                stk.pop();
                stk.top() += tmp ? (tmp * 2) : 1;
            }
            
        }
        return stk.top();
    }
};

py

1
2
def scoreOfParentheses(self, S):
    return eval(S.replace(')(', ')+(').replace('()', '1').replace(')', ')*2'))