leetcode-856-Score-of-Parentheses

发表于   |  

描述

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:

1
2
Input: "()"
Output: 1

Example 2:

1
2
Input: "(())"
Output: 2

Example 3:

1
2
Input: "()()"
Output: 2

Example 4:

1
2
Input: "(()(()))"
Output: 6

分析

类似于 921. Minimum Add to Make Parentheses Valid 这道题，只不过这道题需要根据定义进行计算。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int scoreOfParentheses(String S) {
        Stack<String> stack = new Stack<>();
        for (char c: S.toCharArray()) {
            if (c == '(') {
                stack.push(String.valueOf(c));
            } else {
                int num = 0;
                while (!stack.peek().equals("(")) {
                    num += Integer.parseInt(stack.pop());
                }
                stack.pop();
                stack.push(num == 0 ? String.valueOf("1") : String.valueOf(2*num));
            }
        }
        
        int result = 0;
        while (!stack.empty()) {
            result += Integer.parseInt(stack.pop());
        }
        return result;
    }
}

题目来源