找到第一个外部括号

Question

我需要找到第一个最外层（非嵌套）括号的索引。

例如：

[]                         output: 0, 1
1[2]                       output: 1, 3
3[a2[c]]2[abc]3[cd]        output: 1, 7

我可以通过许多条件找到它，当前代码：

public static void main(String[] args) {
    String input = "3[a2[c]]2[abc]3[cd]ef";
    int first = 0;
    int second = 0;

    int count = 0;
    boolean found = false;
    for (int index = 0; index < input.length(); index++) {
        if (input.charAt(index) == '[') {
            count++;
            if (found == false) {
                found = true;
                first = index;
            }
        } else if (input.charAt(index) == ']') {
            count--;
            if (found && count == 0) {
               second = index;
               break;
            }
        }
    }

    System.out.println(first);
    System.out.println(second);
}

有更加简洁的方法吗？

- xingbin

---

请问您能详细说明一下“first outest”是什么意思吗？ - Shanu Gupta

@ShanuGupta 首先，不是嵌套的。 - xingbin

我认为这还不错。也许你可以用一叠。 - Thiyagu

解决方案非常好...你说的“更简洁”的代码是什么意思？是指不同的算法吗？ - shahaf

添加一个堆栈是没有意义的。你只需要计算打开的数量。 - Patrick Parker

顺便说一句，如果你想要对工作代码进行审查，你应该在codereview stackexchange上发布，而不是在这里。 - Patrick Parker

Answer 1

使用Stack可能更加优雅:

String input = "3[a2[c]]2[abc]3[cd]ef";
Stack<Integer> stack = new Stack<> ();
int first = -1;
int second = -1;

for (int index = 0; index < input.length(); index++) {
    if (input.charAt(index) == '[') {
        stack.push(index);
    } else if (input.charAt(index) == ']' && !stack.isEmpty ()) {
        first = stack.pop ();
        if (stack.isEmpty ()) {
            second = index;
            break;
        }
    }
}

if (first >= 0 && second >= 0) {
    System.out.println(first);
    System.out.println(second);
} else {
  System.out.println ("not found");
}

- Eran

---

谢谢。这样更加优雅。而且由于输入已经正确平衡，我可以删除角落情况的代码。 - xingbin

Answer 2

我想补充一点，使用 stack 可能更加优雅，但会带来额外的 O(n) 空间复杂度，这在某些情况下可能不是理想的选择。

我只是稍微简化了原始计数器策略：

String input = "3[a2[c]]2[abc]3[cd]ef";
int first, second, index, indexOfFirstBracket = input.indexOf('['), count = 1;

for (index = indexOfFirstBracket + 1; index < input.length() && count != 0; index++) {
    if (input.charAt(index) == '[')
        count++;
    else if (input.charAt(index) == ']')
        count--;
}

first = indexOfFirstBracket;
second = index - 1;

System.out.println(first);
System.out.println(second);

这里是我使用 stack 制作的解决方案（我已在代码中添加了注释以进行说明）：

 String input = "3[a2[c]]2[abc]3[cd]ef";
    int first, second, count;
    boolean found = false;

    Stack<Character> stack = new Stack<>();

    // first index will always be fixed
    int indexOfFirstBracket = input.indexOf('[');
    first = indexOfFirstBracket;

    //intialize the stack
    stack.push('[');
    int i;

    //loop from index after first [ character
    for (i = indexOfFirstBracket + 1; i < input.length() && !stack.isEmpty(); i++) {
        if (input.charAt(i) == '[' || (input.charAt(i) == ']' && stack.peek() == ']'))
            stack.push('[');
        else if (input.charAt(i) == ']' && stack.peek() == '[')
            stack.pop();

    }

    // second index when loop breaks
    second = i - 1;

    System.out.println(first);
    System.out.println(second);

假设输入的括号是平衡的。如果需要，我们可以处理它（if second == input.length）。

- Shanu Gupta

---

谢谢回复！ - xingbin

@NengLiu 欢迎。基于堆栈的解决方案会增加空间复杂度。我已经添加了一条注释。 - Shanu Gupta

Answer 3

这里是基于栈的解决方案（希望它能自我解释）。

注意：这假设输入字符串中的括号已经平衡（这在您的代码中是正确的）。

String input = "3[a2[c]]2[abc]3[cd]ef";
Stack<Character> stack = new Stack<>();
int start = input.indexOf("["); //find first '['

System.out.println(start);
for(int i = start + 1   ; i < input.length(); i++) {
    if(input.charAt(i) == '[') {
        stack.push('[');
    } else if (input.charAt(i) == ']') {
        if (stack.isEmpty()) {
            System.out.println(i); //Matching ']' for our first '['
            break;
        }
        stack.pop();
    }
}

- Thiyagu

---

是的，输入已经正确平衡了。谢谢！ - xingbin

Answer 4

我已经消除了其他解决方案所需的一些本地变量。对于条件分支，只有一个简单的操作：堆栈计数要么增加要么减少。

String input = "3[a2[c]]2[abc]3[cd]ef";
int first = input.indexOf('[');
int second = first;
for(int stack = 1; first >= 0 && stack > 0; second++) {     
    switch(input.charAt(second+1)) {
    case '[':
        stack++;
        break;
    case ']':
        stack--;
        break;
    }
}
System.out.println(first);
System.out.println(second);

注意：上述代码依赖于您所述的“]”始终保持平衡的事实。

- Patrick Parker