有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。 如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。 给出一个非空有效字符串 s，求出其原语串的个数。 提示： 1 <= s.length <= 105 s[i] 为 '(' 或 ')' s 是一个有效括号字符串 示例1说明： 输入：s = "(()())(())" 输出：2 解释： 输入字符串为 "(()())(())"，共有 "(()())" 和"(())"两个原语串。以class Solution: def removeOuterParentheses(self, s: str) -> str:为开头

好的，以下是以 `class Solution:` 开头的代码实现：

class Solution:
    def countPrimitives(self, s: str) -> int:
        stack = []
        count = 0
        for c in s:
            if c == '(':
                stack.append(c)
            else:
                stack.pop()
                if not stack:
                    count += 1
        return count

这是 LeetCode 上题目“括号的分数”的 Python 解法，你可以将其复制粘贴到 LeetCode 上进行提交。

相关问题

python有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。 如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。 给出一个非空有效字符串 s，求出其原语串的个数。

好的，这是一个很有趣的问题！其实这个问题可以用栈来解决。具体来说，我们可以遍历字符串 s，用一个栈来记录遍历过程中遇到的左括号。对于每个右括号，如果当前栈顶是左括号，那么就将栈顶弹出，并且原语串的数量加 1；否则就将当前右括号入栈。遍历完整个字符串之后，原语串的数量就是栈中剩余左括号的个数。

以下是 Python 的代码实现：

有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。 如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。 给出一个非空有效字符串 s，求出其原语串的个数。 提示： 1 <= s.length <= 105 s[i] 为 '(' 或 ')' s 是一个有效括号字符串 示例1说明： 输入：s = "(()())(())" 输出：2 解释： 输入字符串为 "(()())(())"，共有 "(()())" 和"(())"两个原语串。

首先，我们可以将问题转化为求所有非空子串中原语串的个数之和。因为如果一个子串是原语串，那么它的所有子串一定都是原语串。

接着，我们可以使用栈来判断一个子串是否为有效括号字符串（即是否存在将其拆分为 A+B 的方法）。具体地，我们遍历字符串，遇到左括号就将其入栈，遇到右括号就将栈顶元素出栈。如果在出栈前栈为空，或者遍历结束后栈非空，那么当前子串就不是有效括号字符串。

最后，我们可以对所有非空子串进行上述判断，如果是有效括号字符串且没有被划分为 A+B 的形式，那么它就是一个原语串。

时间复杂度为 $O(n^2)$，其中 $n$ 是字符串的长度。具体地，外层循环枚举子串的起点，内层循环枚举子串的终点，判断子串是否为原语串的时间复杂度为 $O(n)$。最坏情况下，字符串中所有字符都是左括号，此时所有子串都是有效括号字符串，因此时间复杂度为 $O(n^2)$。

以下是 Python 代码实现：

class Solution:
    def is_valid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '(':
                stack.append(c)
            else:
                if not stack:
                    return False
                stack.pop()
        return not stack

    def countPrimitives(self, s: str) -> int:
        n = len(s)
        count = 0
        for i in range(n):
            for j in range(i, n):
                if self.is_valid(s[i:j+1]) and not ('(' in s[i:j+1] and ')' in s[i:j+1]):
                    count += 1
        return count

可以通过以下代码进行测试：

s = Solution()
print(s.countPrimitives("(()())(())"))  # 输出 2