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
计算由 "(" 和 ")" 组成的字符串的值. 嵌套: 乘 2, 并列: 相加
用 stack 就可以."(" 入栈,")", 往前搜索第一个 "(", 如果中间有数字的, 取出数字求和并乘以 2; 如果没有数字, 直接压入 "1".
最后把 stack 中所有的数字相加.
- class Solution {
- public:
- int scoreOfParentheses(string S) {
- stack<string> s;
- int i = 0;
- while (i < S.length()) {
- if (S[i] == '(')
- s.push("(");
- else {
- if (s.top() == "(") {
- s.pop();
- s.push("1");
- }
- else {
- int temp = 0;
- while (s.top() != "(") {
- temp += stoi(s.top());
- s.pop();
- }
- s.pop();
- s.push(to_string(2 * temp));
- }
- }
- ++i;
- }
- int res = 0;
- while (!s.empty()) {
- res += stoi(s.top());
- s.pop();
- }
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-2657910.html