企业官网建设流程全解析

LeetCode-Go 题解实战：856. Score of Parentheses 括号分数的栈解法与深入剖析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本篇围绕 LeetCode 第 856 题「括号的分数（Score of Parentheses）」展开，以 LeetCode-Go 仓库中 856. Score of Parentheses 解题源码 与测试用例为核心依据，系统讲解题目规则、三种等价解法（栈模拟、按层计分、递归解析）的推导过程，并逐行剖析仓库源码中"以 -1 标记左括号"的栈实现细节与复杂度分析。读完本篇，你将掌握一类"括号字符串评分"问题的通用分析框架，能够独立完成代码复现与正确性验证。

题目理解：三条递归定义规则

原题（见 leetcode/0856.Score-of-Parentheses/README.md）给定一个平衡括号字符串S（balanced parentheses string），要求按下述规则计算其分数：

• ()的分数为1；
• AB的分数为A + B，其中 A、B 均为平衡括号字符串（即并列相加）；
• (A)的分数为2 * A，其中 A 为平衡括号字符串（即包裹翻倍）。

三条规则是递归定义的，因此任意平衡括号串都可以唯一地拆解为"原子()"的组合，分数本质上取决于每个原子()被多少层括号包裹。

官方示例回顾

题目约束：S 是仅含(与)的平衡括号字符串，且2 <= S.length <= 50。长度上限只有 50，意味着递归、栈、DFS 等任何 O(n) 或 O(n²) 级别的解法都可以轻松通过，解题重点在于逻辑清晰与写法优雅。

解法一：栈模拟（仓库采用的核心思路）

解题源码 采用的正是栈方案：遇到(压入标记，遇到)弹出并结算。与常规做法不同，仓库实现用整型栈配合哨兵值-1来充当(的占位标记，避免了额外定义结构体。

package leetcode func scoreOfParentheses(S string) int { res, stack, top, temp := 0, []int{}, -1, 0 for _, s := range S { if s == '(' { stack = append(stack, -1) top++ } else { temp = 0 for stack[top] != -1 { temp += stack[top] stack = stack[:len(stack)-1] top-- } stack = stack[:len(stack)-1] top-- if temp == 0 { stack = append(stack, 1) top++ } else { stack = append(stack, temp*2) top++ } } } for len(stack) != 0 { res += stack[top] stack = stack[:len(stack)-1] top-- } return res }

逐行推演

1. 初始化：res记录最终总分；stack是整数栈；top初始为-1表示空栈；temp在每次右括号结算时临时累加。

2. 遇到(：压入哨兵-1（top++），表示"这里有一层新的包裹"，其内部的分数尚未产生。

3. 遇到)：进入结算流程——

   • temp清零；
   • 从栈顶连续弹出所有非-1的数字并累加到temp，这些数字是当前这一层括号内部并列子串的分数（对应规则AB → A + B）；
   • 弹出顶部的-1哨兵（代表与当前)配对的(）；
   • 关键分支：若temp == 0，说明括号内为空，即原子()，按规则记1分入栈；否则说明内部是若干已完成计分的子串，按规则(A) → 2 * A将temp * 2入栈。

4. 收尾：整个字符串扫描完毕后，栈中剩余的数字是顶层并列的若干组分数，全部累加进res返回。

复杂度分析

• 时间复杂度 O(n)：每个字符入栈/出栈恰好一次，均摊 O(1)，总体 O(n)，n 为字符串长度；
• 空间复杂度 O(n)：最坏情况下（如"((((((((("）栈深度与 n 成正比，因此为 O(n)。

为什么可以用 -1 充当括号标记

栈中只存在两类元素：数字（已结算的分数）与-1 哨兵（未闭合的左括号）。由于题目保证输入是平衡括号串，任意时刻-1的数量恰好等于尚未配对的(数量。以-1作为"分隔层"的妙处在于：遇到)时只需一路弹出数字求和，直到碰到-1即代表这一层的边界，天然实现了"把内层分数汇总后再整体翻倍"的递归语义。

以示例"(()(()))"走一遍（期望输出 6）：

解法二：按层计分（O(n) 且无需显式栈）

从"原子()的分数由包裹层数决定"这一视角出发，可以推导出更精简的按层计数法，这也是 Stack Overflow 上被广泛讨论的标准做法，可当作理解题意的辅助参考：

• 维护变量bal记录当前深度（未闭合的(数量）；
• 从左到右扫描，每当遇到子串"()"（即当前字符是)且前一个字符是(）时，说明这里产生了一个原子括号，其贡献的分数为1 << bal（即2^bal，等价于2 * 2 * ... * 2，共 bal 层包裹）；
• 最终把每个原子括号的贡献累加即得总分。

以"(()(()))"验证：两个原子()分别出现在深度 2 与深度 3 处，贡献2² + 2³ = 4 + 8？注意这并不等于 6——原因在于按层计分法要求原子括号只被其左侧尚未闭合的括号包裹，而第二个原子()前面已有((两层包裹，应为2² = 4。重新数：字符串(()(()))中第一个()位于第 2 层，第二个()位于第 3 层但它是( () ( () ) )中最内层，实际被 3 层包裹，贡献2³ = 8，与第一个的4相加得 12？这依然不等于 6。

这里需要纠正常见误区："包裹层数"指的是该原子左侧所有未闭合(的数量，而不是距离字符串开头的总深度。正确推演：(()(()))的两个原子分别位于第 2 层和第 3 层，若直接按2^depth累加会得到4 + 8 = 12，这显然是错的。正确答案 6 的正确拆解是：内层(())得 2 分，外层整体为( 1 + 2 ) = 3再翻倍得 6。由此可见，按层计分法的正确实现应为遇到()时，用1 << (bal-1)之类按当前包裹深度计数，且只在原子处计分——更稳妥的写法是：扫描时维护bal，当遇到)且前一字符为(时累加1 << (bal - 1)，随后bal--；遇到(时bal++。按此修正，(()(()))：第一个原子在第 2 层计2^(2-1)=2，第二个原子在第 3 层计2^(3-1)=4，合计 6，与题目示例一致。该方法与栈解法本质等价，但省去了显式栈，空间可降至 O(1)。

解法三：递归解析（与题意最贴近的直译）

由于题目规则本身就是递归的，直接按定义翻译成递归同样可行，适合作为讲解辅助思路：

func scoreOfParentheses(S string) int { // 伪代码思路：findScore(l, r) 返回 S[l:r] 的分数 // 1. 若 S[l:r] 形如 "()"，返回 1； // 2. 否则按括号匹配拆出最外层包裹，内部整体翻倍：2 * findScore(l+1, r-1)； // 若内部可拆为多个并列子串，则分别求分后相加。 }

递归实现需要先对字符串做括号配对预处理（记录每个(对应的)位置），最坏情况下时间复杂度为 O(n²)（每次切片后需线性寻找配对），但由于题目 n ≤ 50，仍然完全可接受。三种解法中，栈模拟兼具 O(n) 时间与直观的"即时结算"语义，是实战与面试中最推荐的主方案。

测试验证：以仓库测试用例复现正确性

仓库为本题配备了完整的表驱动测试，位于 856. Score of Parentheses_test.go，覆盖了官方四个示例之外还额外加入了两个边界用例：

测试通过fmt.Printf逐条打印输入与输出（见Test_Problem856），方便肉眼核对。若需在本地运行，可在仓库根目录执行：

# 仅运行本题测试（需先进入对应目录，或使用包路径） go test -v ./leetcode/0856.Score-of-Parentheses/ # 全仓库测试并生成覆盖率（参考仓库 gotest.sh 的写法） go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

仓库根目录的 gotest.sh 展示了统一生成合法覆盖率文件的方式：使用 Go 1.10+ 对多个包一次性-coverprofile，避免旧式 cat 追加导致 Codecov 解析失败的问题，这也是本项目"100% test coverage"质量要求的具体落点（详见仓库根目录 README.md 中关于解题质量的说明）。

举一反三：仓库中的同族括号题目

理解了"哨兵栈"模式后，可以顺带对比仓库中其余括号类题目，它们在数据结构与扫描策略上高度相通：

• 0020.Valid-Parentheses：经典括号配对校验，用栈存左括号字符；
• 0032.Longest-Valid-Parentheses：最长有效括号子串，需要记录下标而非分数；
• 0224.Basic-Calculator：带括号的四则运算求值，同样以栈处理括号优先级；
• 0394.Decode-String：k[encoded_string]解码，是"括号包裹 + 内部展开"思想的字符串版本。

它们的共同抽象是：用栈保存"尚未闭合的上下文"，遇到闭符号时弹出上下文并结算。掌握 856 题的哨兵值技巧后，再遇到这类题目可以快速套用同一分析路径。

小结

LeetCode 856 题的核心是三条递归规则与"包裹翻倍、并列相加"的语义。仓库提供的 Go 实现 用-1哨兵栈在 O(n) 时间内完成全部结算，配合 测试用例 中的六个用例可以完整覆盖嵌套、并列、深层包裹三类场景。无论面试中要求给出栈解法、按层计数还是递归实现，只要抓住"原子()的分数等于2^包裹层数，并列组相加"这一本质，即可举一反三、稳扎稳打。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go