基本递归，检查平衡括号 [英] Basic Recursion, Check Balanced Parenthesis

问题描述

我写的软件在使用堆栈检查平衡方程过去，但现在我要求写一个类似的算法递归检查严格嵌套的括号，括号。

I've written software in the past that uses a stack to check for balanced equations, but now I'm asked to write a similar algorithm recursively to check for properly nested brackets and parenthesis.

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

Good examples: () [] () ([]()[])

坏的例子：（（（[）]

Bad examples: ( (] ([)]

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

Suppose my function is called: isBalanced.

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

Should each pass evaluate a smaller substring (until reaching a base case of 2 left)? Or, should I always evaluate the full string and move indices inward?

推荐答案

有很多方法可以做到这一点，但最简单的算法是简单地处理着左到右，通过堆栈作为参数

There are many ways to do this, but the simplest algorithm is to simply process forward left to right, passing the stack as a parameter

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实现。请注意，我已经关掉，现在这样的在压入堆栈中的前的，而不是在字符串的回的，以方便使用。我还修改了它，使得它只是跳过报告为一个错误的非括号符号来代替。

---

Here it is implemented in Java. Note that I've switched it now so that the stack pushes in front instead of at the back of the string, for convenience. I've also modified it so that it just skips non-parenthesis symbols instead of reporting it as an error.

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

这篇关于基本递归，检查平衡括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！