深入解析：使用栈结构打印字符串中的括号编号

在处理复杂的字符串匹配问题时，我们经常需要跟踪括号的嵌套关系。今天，我们将深入探讨一个经典且实用的编程挑战：如何在一个包含多种字符的字符串中，为每一个括号分配一个唯一的数字编号。这个问题不仅能帮助我们加深对栈数据结构的理解，还在编译器设计、代码格式化工具以及复杂的文本解析场景中有着广泛的应用。

在接下来的内容中，我们将一起探索这个问题的核心逻辑，从简单的概念入手，逐步构建出高效的解决方案。我们将通过多个实际的代码示例，展示如何处理不同类型的括号，并确保我们的代码既健壮又高效。

问题陈述与核心逻辑

我们的任务非常明确：给定一个包含括号（左括号 INLINECODE7d654a2c 和右括号 INLINECODEbfb95200）以及其他字符的字符串，我们需要遍历这个字符串，并为每一个出现的括号分配一个整数编号。

分配规则如下：

• 左括号 ‘(‘：我们按照其在字符串中出现的顺序，依次分配递增的编号。第一个出现的左括号编号为 1，第二个为 2，以此类推。
• 右括号 ‘)‘：其编号必须与它所匹配的左括号的编号保持一致。这意味着，如果一个右括号关闭了编号为 2 的左括号，那么该右括号的编号也应该是 2。

为了更直观地理解这一点，让我们先来看一个具体的例子。

#### 示例分析 1：平衡的嵌套

输入： "(aa(bdc))p(dee)"
输出： 1 2 2 1 3 3
逐步解析：

• 首先，我们遇到了第一个左括号 INLINECODEd43297cd，分配编号 INLINECODEcce830b8。当前结果：INLINECODEcbde2414。栈中保存：INLINECODE83d605b0。
• 紧接着是字符 ‘a‘, ‘a‘，忽略。
• 遇到第二个左括号 INLINECODEc3ebedd7，分配新编号 INLINECODE0422b64e。当前结果：INLINECODE6fec70a8。栈中保存：INLINECODE17901715。
• 字符 ‘b‘, ‘d‘, ‘c‘ 被忽略。
• 遇到第一个右括号 INLINECODEfd14fd8a，它对应的是栈顶的左括号（编号 2）。弹出栈顶的 2 并加入结果。当前结果：INLINECODE04f91b4f。栈中保存：[1]。
• 遇到第二个右括号 INLINECODE80ba41d4，它对应的是剩余的栈顶左括号（编号 1）。弹出栈顶的 1 并加入结果。当前结果：INLINECODE618d1c3c。栈中保存：[]。
• 字符 ‘p‘ 被忽略。
• 遇到第三个左括号 INLINECODE82ee31c0，分配新编号 INLINECODE99a2274e。当前结果：INLINECODE79f72aee。栈中保存：INLINECODE8434b26e。
• 字符 ‘d‘, ‘e‘, ‘e‘ 被忽略。
• 遇到第三个右括号 INLINECODEaf8a4092，对应栈顶编号 3。弹出并加入。最终结果：INLINECODE15efb674。

#### 示例分析 2：连续的左括号

有时候，输入可能不会完美地闭合，或者会出现连续的左括号。我们的算法同样需要稳健地处理这些情况。

输入： "(((()("
输出： 1 2 3 4 4 5
解析：

这里我们连续遇到了 4 个左括号。前三个得到 1, 2, 3。第四个得到 4。接着一个右括号匹配了最近的 4。最后又是一个左括号，分配新的编号 5。这个例子展示了计数器是如何一直递增的，无论之前的括号是否闭合。

算法设计与数据结构

通过上述例子，你可能已经敏锐地发现了一个关键模式：后进先出（LIFO）。对于右括号，我们总是需要找到离它最近的、尚未被匹配的左括号。这正是栈数据结构的典型应用场景。

我们的核心策略：

• 初始化：我们需要一个计数器 INLINECODE6f2ed570（或者叫 INLINECODEc2758cea）来记录当前是第几个左括号；一个栈 INLINECODE5168e7a4 来暂存遇到的左括号编号；以及一个列表 INLINECODEa662a90d 来存储最终的输出序列。
• 遍历字符串：逐个字符检查。
• 遇到左括号 ‘(‘：

* 计数器 bal 加 1。

* 将 INLINECODEe47a5163 的值推入栈 INLINECODE1c279922 中（表示这个编号的括号 "开启" 了）。

* 将 INLINECODE375e0e20 的值追加到结果列表 INLINECODE9060089f 中。

• 遇到右括号 ‘)‘：

* 检查栈顶元素（如果栈为空，说明输入格式有误，但在本题假设中我们通常默认输入合法或只需处理匹配情况）。

* 将栈顶元素弹出，并追加到结果列表 res 中。

* 此时计数器 bal 保持不变，因为它记录的是历史上遇到的左括号总数，而不是当前的深度。

• 其他字符：直接忽略，不进行任何操作。

深入代码实现

现在，让我们将这个逻辑转化为具体的代码。为了确保你能在任何技术栈下都能应对自如，我为你准备了 C++、Java、Python、C# 和 JavaScript 五种主流语言的完整实现。请注意代码中的注释，它们解释了每一行代码背后的意图。

#### C++ 实现

C++ 以其高性能和对底层内存的控制著称，非常适合处理大规模的字符串解析任务。

#include 
#include 
#include 
#include 

using namespace std;

/* 
 * 函数：bracketNumbers
 * 功能：遍历字符串并生成括号编号序列
 * 参数：str - 输入的字符串引用
 * 返回值：包含所有括号编号的整数向量
 */
vector bracketNumbers(string &str) {
    vector res;       // 用于存储最终的结果序列
    stack st;         // 栈，用于存储还未被匹配的左括号编号
    
    int count = 0;         // 计数器，记录当前遇到的左括号总数
    
    // 遍历字符串中的每一个字符
    for (int i = 0; i < str.size(); i++) {
        // 如果是左括号
        if (str[i] == '(') {
            count++;                 // 增加计数
            res.push_back(count);    // 将编号加入结果
            st.push(count);          // 将编号压入栈中，等待匹配
        }
        // 如果是右括号
        else if (str[i] == ')') {
            // 弹出栈顶的编号（即与之匹配的左括号编号）
            // 并将其加入结果列表
            res.push_back(st.top());
            st.pop();
        }
        // 其他字符直接忽略
    }

    return res;
}

int main() {
    // 测试用例 1
    string str = "(aa(bdc))p(dee)";
    vector result = bracketNumbers(str);
    
    cout << "输入: " << str << endl;
    cout << "输出: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

#### Java 实现

Java 的集合框架提供了非常方便的 INLINECODE411bf8e4 类和 INLINECODEba1edfdc 接口，使得代码逻辑非常清晰。

import java.util.Stack;
import java.util.ArrayList;
import java.util.List;

public class BracketLabeler {
    
    public static List bracketNumbers(String str) {
        List res = new ArrayList(); // 结果列表
        Stack st = new Stack();     // 栈
        int count = 0;                         // 计数器
        
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(') {
                count++;                  // 递增计数
                res.add(count);          // 记录左括号编号
                st.push(count);           // 入栈
            } else if (c == ')') {
                // 遇到右括号，取出栈顶元素作为编号
                res.add(st.pop()); 
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String input = "(((()(";
        List result = bracketNumbers(input);
        
        System.out.print("输入: " + input + "
输出: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

#### Python 实现

Python 的列表既可以作为动态数组，也可以作为栈使用（通过 INLINECODE901db012 和 INLINECODEd4c7d116 操作）。这种简洁性使其成为快速原型开发的首选。

def bracket_numbers(s):
    res = []   # 结果列表
    st = []    # 用列表模拟栈
    count = 0  # 计数器
    
    for char in s:
        if char == ‘(‘:  
            count += 1      # 增加计数
            res.append(count) # 记录编号
            st.append(count) # 入栈
        elif char == ‘)‘:
            # 弹出栈顶元素并记录
            res.append(st.pop())
            
    return res

if __name__ == ‘__main__‘:
    # 测试多个用例
    test_cases = [
        "(aa(bdc))p(dee)",
        "(((()(",
        "()()()"
    ]
    
    for s in test_cases:
        result = bracket_numbers(s)
        print(f"输入: {s}")
        print(f"输出: {‘ ‘.join(map(str, result))}")
        print("-" * 20)

#### C# 实现

C# 提供了强类型的泛型集合，代码结构严谨，非常适合在 .NET 环境下进行企业级开发。

using System;
using System.Collections.Generic;

class Program {
    // 获取括号编号的方法
    static List BracketNumbers(string str) {
        List res = new List(); // 结果列表
        Stack st = new Stack(); // 栈
        int count = 0;                    // 计数器
        
        foreach (char c in str) {
            if (c == ‘(‘) {
                count++;
                res.Add(count); // 记录左括号编号
                st.Push(count);  // 压入栈
            } else if (c == ‘)‘) {
                // 弹出栈顶并记录
                res.Add(st.Pop());
            }
        }
        return res;
    }

    static void Main() {
        string str = "(aa(bdc))p(dee)";
        List result = BracketNumbers(str);
        
        Console.WriteLine("输出: " + string.Join(" ", result));
    }
}

#### JavaScript 实现

在现代 Web 开发中，JavaScript 的数组方法非常灵活。我们可以直接使用数组来实现栈逻辑。

function bracketNumbers(str) {
    let res = []; // 结果数组
    let st = [];  // 栈数组
    let count = 0; // 计数器
    
    for (let char of str) {
        if (char === ‘(‘) {
            count++;
            res.push(count);
            st.push(count);
        } else if (char === ‘)‘) {
            // pop() 移除并返回最后一个元素
            res.push(st.pop());
        }
    }
    return res;
}

// 测试
const str = ‘(aa(bdc))p(dee)‘;
const result = bracketNumbers(str);
console.log(‘输出:‘, result.join(‘ ‘));

复杂度分析与性能优化

在编写生产级代码时，我们需要时刻关注算法的效率。

• 时间复杂度：我们只对字符串进行了一次遍历。在遍历过程中，对于每个字符，无论是入栈还是弹出操作，都只消耗常数时间 O(1)。因此，总体时间复杂度为 O(n)，其中 n 是字符串的长度。这是理论上最优的解法，因为你至少要看一遍字符串才能知道括号在哪里。

• 空间复杂度：在最坏的情况下，如果字符串全部由左括号组成（例如 "((((..."），栈的大小将增长到 n。因此，辅助空间复杂度为 O(n)。这同样是必须的，因为我们需要存储这些信息以确保右括号能正确匹配。

优化建议：

虽然上述方案已经是标准解法，但在内存极其受限的嵌入式系统中，如果输入字符串非常巨大且括号嵌套极深，可能需要考虑是否能复用输入字符串的存储空间来存储结果，或者使用位操作来压缩编号（如果括号数量不超过特定限制）。但在常规应用开发中，上述栈实现是最佳平衡点。

常见误区与解决方案

当你开始动手实践时，可能会遇到一些棘手的问题。以下是我们在开发过程中容易犯的错误：

• 混淆计数器与栈深度：

错误*：在遇到右括号时，试图使用计数器减 1 来作为编号。
解释*：计数器 INLINECODEa1e48218 代表的是 "历史上遇到的第几个左括号"，它只增不减。而右括号的编号取决于它匹配的是 "哪一个" 左括号，这个信息必须由栈顶提供。例如，输入 INLINECODE3d47ef61，如果用计数器减一，第二个右括号可能会被错误地编号为 1（如果逻辑写错）而不是 2。正确的编号应该是 1 2 2 1。

• 忽略非括号字符：

错误*：在循环中处理了所有字符，或者错误地将字母也压入了栈。
解释*：务必在循环体内加入 INLINECODE3ecffde9 判断，只有 INLINECODE6dd9c73e 和 INLINECODE4f523d57 才触发核心逻辑，其他字符应直接 INLINECODEb82eb8b2 或忽略。

• 空栈异常：

错误*：遇到右括号时直接调用 INLINECODEfbb54e6d 或 INLINECODE897a5cb7 而没有检查栈是否为空。
解释*：如果输入是不合法的（比如以 INLINECODE6d7d33be 开头），直接操作空栈会导致程序崩溃。虽然本题通常假设输入合法，但健壮的代码应该先检查 INLINECODE72459580。

实战应用场景

掌握了这个算法，你实际上就已经具备了处理以下实际问题的能力：

• 代码编辑器的括号匹配高亮：当你把光标放在一个右括号上，编辑器是如何知道高亮哪个左括号的？原理基本相同。编辑器通常不打印编号，而是直接利用栈中存储的位置索引来定位字符位置。

• 计算器程序：在编写支持括号的计算器时（例如计算 "3 + (2 * (5 - 1))"），我们需要知道每个右括号对应的是哪一层运算优先级。栈结构在这里起到了决定性的作用。

• JSON/XML 解析器：在解析嵌套的数据结构时，验证标签的闭合顺序也是基于类似的逻辑。

总结

在这篇文章中，我们通过一个看似简单的 "打印括号编号" 问题，深入探讨了栈这一基础数据结构的强大之处。我们了解到，通过维护一个简单的计数器和一个栈，我们就能以 O(n) 的时间复杂度完美解决括号匹配和编号的问题。

我们不仅提供了五种主流语言的实现代码，还分析了潜在的陷阱和实际应用中的价值。编程的魅力往往在于这些基础算法的灵活运用。希望你在阅读完这篇文章后，下次再遇到括号匹配的问题时，能自信地写出优雅且高效的代码。

现在，轮到你了！试着修改上述代码，看看能否让它支持大括号 INLINECODE711ae8ac 和中括号 INLINECODE53f4ee8f 的编号？或者尝试打印出每个括号对在原字符串中的索引位置？继续探索，你会发现更多编程的乐趣。