基本recursion，检查平衡括号

我已经编写了过去使用堆栈来检查平衡方程的软件，但是现在我被要求recursion地编写一个类似的algorithm来检查正确嵌套的括号和括号。

好例子:(）[]（）（[]（）[]）

不好的例子：（（]（[）]

假设我的函数被调用：isBalanced。

应该每次通过评估一个较小的子string（直到达到左边的基本情况）？ 或者，我是否应该总是评估整个string并向内移动索引？

Answer 1

有很多方法可以做到这一点，但最简单的algorithm是简单地从左向右进行处理，将堆栈作为parameter passing

FUNCTION isBalanced(String input, String stack) : boolean IF isEmpty(input) RETURN isEmpty(stack) ELSE IF isOpen(firstChar(input)) RETURN isBalanced(allButFirst(input), stack + firstChar(input)) ELSE IF isClose(firstChar(input)) RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack)) AND isBalanced(allButFirst(input), allButLast(stack)) ELSE ERROR "Invalid character" 

---

这里用Java实现。 请注意，为了方便起见，我现在已经把它切换了，以便栈在前面而不是在string的后面 。 我也修改了它，以便它跳过非括号符号，而不是将其报告为错误。

 static String open = "([<{"; static String close = ")]>}"; static boolean isOpen(char ch) { return open.indexOf(ch) != -1; } static boolean isClose(char ch) { return close.indexOf(ch) != -1; } static boolean isMatching(char chOpen, char chClose) { return open.indexOf(chOpen) == close.indexOf(chClose); } static boolean isBalanced(String input, String stack) { return input.isEmpty() ? stack.isEmpty() : isOpen(input.charAt(0)) ? isBalanced(input.substring(1), input.charAt(0) + stack) : isClose(input.charAt(0)) ? !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0)) && isBalanced(input.substring(1), stack.substring(1)) : isBalanced(input.substring(1), stack); } 

testing装置：

  String[] tests = { "()[]<>{}", "(<", "]}", "()<", "(][)", "{(X)[XY]}", }; for (String s : tests) { System.out.println(s + " = " + isBalanced(s, "")); } 

输出：

 ()[]<>{} = true (< = false ]} = false ()< = false (][) = false {(X)[XY]} = true 

Answer 2

首先，对于您的原始问题，请注意，如果您使用的string非常长，则不必在每次进行函数调用时都将精确副本减去一个字母。 所以你应该赞成使用索引或者validation你select的语言不是在幕后复制的。

其次，我在这里使用堆栈数据结构的所有答案都有问题。 我认为你的任务的重点是让你明白，recursion你的函数调用创build一个堆栈 。 您不需要使用堆栈数据结构来保存圆括号，因为每个recursion调用都是隐式堆栈上的新条目。

我将演示一个与(和)匹配的C程序。 添加像[和]的其他types是读者的练习。 所有我在函数中维护的是我在string中的位置（作为指针传递），因为recursion是我的堆栈。

 /* Search a string for matching parentheses. If the parentheses match, returns a * pointer that addresses the nul terminator at the end of the string. If they * don't match, the pointer addresses the first character that doesn't match. */ const char *match(const char *str) { if( *str == '\0' || *str == ')' ) { return str; } if( *str == '(' ) { const char *closer = match(++str); if( *closer == ')' ) { return match(++closer); } return str - 1; } return match(++str); } 

testing这个代码：

  const char *test[] = { "()", "(", ")", "", "(()))", "(((())))", "()()(()())", "(() ( hi))) (())()(((( ))))", "abcd" }; for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) { const char *result = match(test[index]); printf("%s:\t", test[index]); *result == '\0' ? printf("Good!\n") : printf("Bad @ char %d\n", result - test[index] + 1); } 

输出：

 (): Good! (: Bad @ char 1 ): Bad @ char 1 : Good! (())): Bad @ char 5 (((()))): Good! ()()(()()): Good! (() ( hi))) (())()(((( )))): Bad @ char 11 abcd: Good! 

Answer 3

这个想法是保留一个被打开的括号的列表，如果你发现一个闭包，检查它是否closures最后打开的：

• 如果这些括号匹配，则从已打开的束的列表中删除上次打开的对象，并继续recursion地检查string的其余部分
• 否则，你已经发现了一个closures一个神经的括号，所以它是不平衡的。

当string最后为空时，如果括号列表也是空的（所以括号已经closures）返回true ，否则返回false

algorithm （用Java）：

 public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) { if ((str1 == null) || str1.isEmpty()) { return openedBrackets.isEmpty(); } else if (closeToOpen.containsValue(str1.charAt(0))) { openedBrackets.add(str1.charAt(0)); return isBalanced(str1.substring(1), openedBrackets, closeToOpen); } else if (closeToOpen.containsKey(str1.charAt(0))) { if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) { openedBrackets.removeLast(); return isBalanced(str1.substring(1), openedBrackets, closeToOpen); } else { return false; } } else { return isBalanced(str1.substring(1), openedBrackets, closeToOpen); } } 

testing ：

 public static void main(final String[] args) { final Map<Character, Character> closeToOpen = new HashMap<Character, Character>(); closeToOpen.put('}', '{'); closeToOpen.put(']', '['); closeToOpen.put(')', '('); closeToOpen.put('>', '<'); final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" }; for (final String test : testSet) { System.out.println(test + " -> " + isBalanced(test, new LinkedList<Character>(), closeToOpen)); } } 

输出 ：

 abcdefksdhgs -> true [{aaa<bb>dd}]<232> -> true [ff{<gg}]<ttt> -> false {<}> -> false 

请注意，我已经导入了以下类：

 import java.util.HashMap; import java.util.LinkedList; import java.util.Map; 

Answer 4

  public static boolean isBalanced(String str) { if (str.length() == 0) { return true; } if (str.contains("()")) { return isBalanced(str.replaceFirst("\\(\\)", "")); } if (str.contains("[]")) { return isBalanced(str.replaceFirst("\\[\\]", "")); } if (str.contains("{}")) { return isBalanced(str.replaceFirst("\\{\\}", "")); } else { return false; } } 

Answer 5

从逻辑的angular度来看，这并不重要 – 如果你保存了一堆所有当前不平衡的parens，而这些parens是你递交给recursion的每一步的，那么你永远不需要向后看，所以它不会如果你在每次recursion调用时都切断了string，或者只是增加一个索引而只查看当前的第一个字符，那么问题很重要。

在绝大多数具有不可变string的编程语言中，缩短string可能比在string中传递稍大的string更昂贵（性能方面）。 另一方面，像C这样的语言，你可以只增加char数组中的指针。 我想这很有赖于语言，这两种方法哪一种更“高效”。 从概念的angular度来看，它们都是等价的。

Answer 6

我会说这取决于你的devise。 你可以使用两个计数器或者用两个不同的符号堆栈，或者你可以使用recursion来处理它，不同之处在于devise方法。

Answer 7

 func evalExpression(inStringArray:[String])-> Bool{ var status = false var inStringArray = inStringArray if inStringArray.count == 0 { return true } // determine the complimentary bracket. var complimentaryChar = "" if (inStringArray.first == "(" || inStringArray.first == "[" || inStringArray.first == "{"){ switch inStringArray.first! { case "(": complimentaryChar = ")" break case "[": complimentaryChar = "]" break case "{": complimentaryChar = "}" break default: break } }else{ return false } // find the complimentary character index in the input array. var index = 0 var subArray = [String]() for i in 0..<inStringArray.count{ if inStringArray[i] == complimentaryChar { index = i } } // if no complimetary bracket is found,so return false. if index == 0{ return false } // create a new sub array for evaluating the brackets. for i in 0...index{ subArray.append(inStringArray[i]) } subArray.removeFirst() subArray.removeLast() if evalExpression(inStringArray: subArray){ // if part of the expression evaluates to true continue with the rest. for _ in 0...index{ inStringArray.removeFirst() } status = evalExpression(inStringArray: inStringArray) } return status } 

Answer 8

PHP解决scheme来检查平衡括号

 <?php /** * @param string $inputString */ function isBalanced($inputString) { if (0 == strlen($inputString)) { echo 'String length should be greater than 0'; exit; } $stack = array(); for ($i = 0; $i < strlen($inputString); $i++) { $char = $inputString[$i]; if ($char === '(' || $char === '{' || $char === '[') { array_push($stack, $char); } if ($char === ')' || $char === '}' || $char === ']') { $matchablePairBraces = array_pop($stack); $isMatchingPair = isMatchingPair($char, $matchablePairBraces); if (!$isMatchingPair) { echo "$inputString is NOT Balanced." . PHP_EOL; exit; } } } echo "$inputString is Balanced." . PHP_EOL; } /** * @param string $char1 * @param string $char2 * @return bool */ function isMatchingPair($char1, $char2) { if ($char1 === ')' && $char2 === '(') { return true; } if ($char1 === '}' && $char2 === '{') { return true; } if ($char1 === ']' && $char2 === '[') { return true; } return false; } $inputString = '{ Swatantra (() {} ()) Kumar }'; isBalanced($inputString); ?> 

Answer 9

在Scala编程语言中，我会这样做：

  def balance(chars: List[Char]): Boolean = { def process(chars: List[Char], myStack: Stack[Char]): Boolean = if (chars.isEmpty) myStack.isEmpty else { chars.head match { case '(' => process(chars.tail, myStack.push(chars.head)) case ')' => if (myStack.contains('(')) process(chars.tail, myStack.pop) else false case '[' => process(chars.tail, myStack.push(chars.head)) case ']' => { if (myStack.contains('[')) process(chars.tail, myStack.pop) else false } case _ => process(chars.tail, myStack) } } val balancingAuxStack = new Stack[Char] process(chars, balancingAuxStack) } 

请编辑，使其完美。

我只是build议在Scala中进行转换。

Answer 10

它应该是一个简单的使用堆栈..

 private string tokens = "{([<})]>"; Stack<char> stack = new Stack<char>(); public bool IsExpressionVaild(string exp) { int mid = (tokens.Length / 2) ; for (int i = 0; i < exp.Length; i++) { int index = tokens.IndexOf(exp[i]); if (-1 == index) { continue; } if(index<mid ) stack .Push(exp[i]); else { if (stack.Pop() != tokens[index - mid]) { return false; } } } return true; } 

Answer 11

@个人的答案很好，足以解决圆括号的语法问题。 如果你想使用堆栈或不想使用recursion方法，你可以看看github上的python 脚本 。 它简单快捷。

 BRACKET_ROUND_OPEN = '(' BRACKET_ROUND__CLOSE = ')' BRACKET_CURLY_OPEN = '{' BRACKET_CURLY_CLOSE = '}' BRACKET_SQUARE_OPEN = '[' BRACKET_SQUARE_CLOSE = ']' TUPLE_OPEN_CLOSE = [(BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE), (BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE), (BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE)] BRACKET_LIST = [BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE,BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE,BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE] def balanced_parentheses(expression): stack = list() left = expression[0] for exp in expression: if exp not in BRACKET_LIST: continue skip = False for bracket_couple in TUPLE_OPEN_CLOSE: if exp != bracket_couple[0] and exp != bracket_couple[1]: continue if left == bracket_couple[0] and exp == bracket_couple[1]: if len(stack) == 0: return False stack.pop() skip = True left = '' if len(stack) > 0: left = stack[len(stack) - 1] if not skip: left = exp stack.append(exp) return len(stack) == 0 if __name__ == '__main__': print(balanced_parentheses('(()())({})[]'))#True print(balanced_parentheses('((balanced)(parentheses))({})[]'))#True print(balanced_parentheses('(()())())'))#False