Given a balanced parentheses string S, compute the score of the string based on the following rule:
() has score 1AB 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 <= 50class Solution { public int scoreOfParentheses(String S) { Stack<Integer> stack = new Stack(); int cur = 0; for(char c : S.toCharArray()) { if(c == ‘(‘) { stack.push(cur); cur = 0; } else { cur = stack.pop() + Math.max(1, 2 * cur); } } return cur; } }
https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space
原文：https://www.cnblogs.com/wentiliangkaihua/p/14444879.html