单括号匹配算法：核心原理与 C++ 高效实现

案例 2：非法序列 ( ) )

这两张表完美诠释了「过程平衡 + 最终平衡」的核心逻辑。

四、算法原理深度讲解

单括号匹配的本质是「动态平衡维护」：左括号是增量，右括号是减量。全程不允许减量超过增量（balance ≥ 0），最终增量与减量完全抵消（balance = 0）。

该方案性能达到理论最优：

• 时间复杂度：O(n) —— 仅需遍历字符串一次，无嵌套循环；
• 空间复杂度：O(1) —— 仅使用一个整型变量，无额外空间开销。

这是单括号匹配问题无法被超越的最优解法。

五、C++ 关键代码实现与讲解

以下是精简、高效且工业级的 C++ 代码实现，我们逐行解析其中的工程细节。

#include <iostream>
#include <string>
using namespace std;

// 判断单括号（仅小括号）序列是否合法
bool isValidParentheses(const string& str) {
    // 平衡值：记录左括号 - 右括号的差值
    int balance = 0;

    // 遍历字符串每一个字符
    for (char ch : str) {
        if (ch == '(') {
            // 左括号：平衡值 +1
            balance++;
        } else if (ch == ')') {
            // 右括号：平衡值 -1
            balance--;
        }

        // 关键：中途出现负数 → 右括号过多，直接非法
        if (balance < 0) {
            return false;
        }
    }

    // 最终平衡值必须为 0 → 左右括号数量相等
    return balance == 0;
}

int main() {
    // 测试用例
    string s1 = "((()))"; // 合法
    string s2 = "())";    // 非法

    cout << boolalpha;
    cout << "测试用例 1 结果：" << isValidParentheses(s1) << endl;
    cout << "测试用例 2 结果：" << isValidParentheses(s2) << endl;

    return 0;
}

代码核心亮点

1. 常量引用传参：const string& 避免拷贝大对象，提升性能；
2. 提前终止：一旦 balance < 0 立即返回，无需遍历完整个字符串，节省时间；
3. 极致简洁：无冗余逻辑，一行一动作，可读性与效率拉满。

六、算法思维的启示

单括号匹配虽简单，却藏着算法设计的顶级智慧：

1. 简化问题：先剥离所有干扰，聚焦核心矛盾；
2. 消除冗余：能用一个变量解决的问题，绝不用两个；
3. 提前剪枝：发现非法立即终止，不做无用功；
4. 平衡思想：这是算法、数据结构乃至计算机系统设计中最常用的核心思想。

很多时候，优雅的算法不是「灵机一动」，而是对问题本质的深度洞察。

七、结语

一对括号，一串序列，一次遍历，一份平衡。单括号匹配是算法世界里最朴素的浪漫，它用最精简的代码实现最高效的逻辑。当你真正读懂这几行代码背后的思维，便已经推开了算法世界的第一扇大门。