找到第一个外括号

我需要找出第一个最外层（不是嵌套）括号索引。

例如

[] 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); } 

有更clean方法吗？

Answer 1

使用Stack可能更优雅：

 String input = "3[a2[c]]2[abc]3[cd]ef"; Stack 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"); } 

Answer 2

我想补充一点，使用stack可能更优雅但是增加了O(n) space complexity ，这在所有情况下可能都不可取。

我只是稍微缩小了OP的原始计数器策略：

 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 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 ）。

Answer 3

这是一个基于堆栈的解决方案（我希望它是不言自明的）

注意：这假定输入字符串中的括号已正确平衡（代码中就是这种情况）。

 String input = "3[a2[c]]2[abc]3[cd]ef"; Stack 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(); } } 

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); 

注意：上面的代码依赖于这样的事实，即如你所说的那样，将始终保持平衡。