基本递归，检查平衡括号

Question

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

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

较差实施：（（（[）]

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

如果每次通过评估一个较小的子串（直到达到2人给出了基本情况）？或者，我应该始终评估满弦和向内移动指标？

Answer 1

有很多方法可以做到这一点，但最简单的算法是简单的进程向前推进从左到右，通过堆栈作为参数

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实现。请注意，为了方便起见，我现在已经切换了它，以便堆栈推入前面的而不是后面的。我还修改了它，以便它跳过非括号符号而不是将其报告为错误。

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

测试工具：

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

输出：

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

Answer 2

我会说这取决于你的设计。您可以使用两个计数器或使用两个不同的符号堆栈，或者您可以使用递归处理它，差别在于设计方法。

Answer 3

从逻辑的角度来看，这并不重要 - 如果你保留了所有当前不平衡的parens的堆栈，你将传递给递归的每一步，你永远不需要向后看，所以如果在每次递归调用时切断字符串，或者只是增加索引并仅查看当前的第一个字符，则无关紧要。

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

Answer 4

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

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 5

首先，你原来的问题，请注意，如果你的工作时间很长，戒指，每次进行函数调用时，您都不希望将精确副本减去单个字母。所以你应该喜欢使用索引或者验证你选择的语言不是在幕后制作副本。

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

我将用一个与(和)匹配的C程序进行演示。添加像[和]这样的其他类型是读者的练习。我在函数中维护的所有内容都是我在字符串中的位置（作为指针传递），因为递归是我的堆栈。

/* 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); 
} 

经过测试与验证码：

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 6

的想法是保持打开的括号的列表，如果你找到一个封闭brackt，检查是否它关闭最后打开的：

• 如果这些括号匹配，然后从已打开的束的列表中删除最后打开的并继续对字符串的其余部分递归检查
• 否则您发现一个括号会关闭一次打开的神经，因此它不平衡。

当弦终于空，如果brackes的列表为空太（所以所有的brackes已关闭）返回true，否则false

算法（在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); 
    } 
} 

TEST：

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 7

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 8

@逐张的回答是好的，足以解决括号语法问题。如果你想使用堆栈或不想使用递归方法，你可以看看github上的python script。它简单而快速。

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 

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

请修改，使其完美。

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

Answer 10

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 11

PHP解决方案，以检查平衡括号

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