856.括号的分数

链接：856.括号的分数
难度：Medium
标签：栈、字符串
简介：给定一个平衡括号字符串  S，按下述规则计算该字符串的分数：() 得 1 分。AB 得  A + B  分，其中 A 和 B 是平衡括号字符串。(A) 得  2 * A  分，其中 A 是平衡括号字符串。

题解 1 - java

• 编辑时间：2020-02-16
• 执行用时：4ms
• 内存消耗：41.3MB
• 编程语言：java
• 解法介绍：左括号压栈，右括号时判断当前括号里是否含有*，含有则出栈并把个数*2，最后算*的个数。

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Character> stack = new Stack<Character>();
		int len = S.length();
		int sum = 0, tem = 0;
		for (int i = 0; i < len; i++) {
//			System.out.println(stack + ",sum:" + sum + ",tem:" + tem);
			char c = S.charAt(i);
			if (c == '(') {
				stack.push(c);
			} else {
				char d = stack.pop();
				if (d == '(') {
					stack.push('*');
				}
				if (d == '*') {
					tem++;
					while (stack.pop() == '*') {
						tem++;
					}
					tem *= 2;
//					System.out.println(stack);
//					System.out.println(tem);
					while (tem != 0) {
						stack.push('*');
						tem--;
					}
//					System.out.println(stack);
				}
			}
		}
		while (!stack.isEmpty()) {
			stack.pop();
			sum++;
		}
		return sum;
    }
}

题解 2 - cpp

• 编辑时间：2022-10-09
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：栈。

class Solution {
public:
    int scoreOfParentheses(string s) {
        vector<int> st;
        for (auto &c : s) {
            if (c == '(') {
                st.push_back(-1);
            } else if (st.back() == -1) {
                st.pop_back();
                st.push_back(1);
            } else {
                int num = 0;
                while (st.back() != -1) {
                    num += st.back();
                    st.pop_back();
                }
                st.pop_back();
                st.push_back(num * 2);
            }
        }
        return accumulate(st.begin(), st.end(), 0);
    }
};