Java C++题解leetcode856括号的分数

下面我将为你详细讲解“Java C++题解leetcode856括号的分数”的完整攻略。

题目描述

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例1：

输入： "()"
输出： 1

示例2：

输入： "(())"
输出： 2

解题思路

该题可以使用栈（Stack）来解决。遍历字符串，遇到左括号就将其入栈，遇到右括号就弹出栈顶元素，进行计算。需要注意的是，对于括号的分数计算，需要遵循题目的规则，即根据括号的类型进行不同的计算。

以示例2 "(())" 为例，其遍历过程与操作栈如下所示：

字符	操作栈	分数	总分数
(	(		0
(	(,(		0
)		1	1
)		1	2

对于括号的计算，可以使用一个变量来记录当前遍历的块的分数，遇到左括号时，将该变量压入栈中，遇到右括号时，弹出栈顶元素进行计算。判断当前块的括号类型时，可以使用一个变量记录左括号的数量，遇到左括号时加一，遇到右括号时减一。如果当前块的括号数量为零，则说明当前块为有效的括号序列，进行相应分数的计算即可。

代码实现

Java代码实现：

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>(); // 建立栈
        int score = 0; // 分数
        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(score); // 左括号的分数入栈
                score = 0; // 清零score
            } else {
                score = stack.pop() + Math.max(score * 2, 1); // 计算分数
            }
        }
        return score; // 返回总分数
    }
}

C++代码实现：

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> stk; // 建立栈
        int score = 0; // 分数
        for (char c : S) {
            if (c == '(') {
                stk.push(score); // 左括号的分数入栈
                score = 0; // 清零score
            } else {
                score = stk.top() + max(score * 2, 1); // 计算分数
                stk.pop(); // 弹出栈顶元素
            }
        }
        return score; // 返回总分数
    }
};

总结

通过使用栈来解决该题，可以很容易地完成对字符串中括号的分数计算。需要注意的是，在计算分数时，需要遵循题目的规则，即根据括号的类型进行不同的计算。