判断包含括号的字符串是否平衡

Question

这是我已经尝试解决一个星期的学校作业，我仍然没有接近真正的答案。如果有人如此友善并以一些可靠的指导指导我，那将是非常感激的，注意我不想要解决方案。例如，字符串 () 、 [()] 、 {([])} 、 ()[] 是 4 个平衡字符串。

编写递归方法：`

public static boolean isBalanced(String in)

如果 in 是一个平衡的括号字符串并且 returns 为真如果不是，则为 false。

这是我一直在研究的一些代码：

    public static boolean isBalanced(String in){
        if(in.length() == 0){
            return true;
        }
        char aux = in.charAt(0);
        if(aux == '{' ||aux == '[' ||aux == '(' ){
            if(aux == '{'){
                return isBalanced(in.substring(1));
            }
            if(aux == '}'){
                return false || isBalanced(in.substring(1));
            }
            if(aux == '['){
                return isBalanced(in.substring(1));
            }
            if(aux == ']'){
                return false || isBalanced(in.substring(1));
            }if(aux == '('){
                return isBalanced(in.substring(1));
            }
            if(aux == ')'){
                return false || isBalanced(in.substring(1));
            }
        }
        return isBalanced(in.substring(1));
    }   

}

Answer 1

由于您不需要复制粘贴解决方案，因此您应该查看此 post：

它是用PHP写的，但解释了背后的想法，你可以很容易地适应。 "validate" 您输入的页面仍然可用：http://dog-net.org/string.php，因此您可以测试 "huge" 个字符串而无需进行文书工作。

根据您的意见，您需要实施递归方法。因此，对于 isbalanced(String str) 的 given signature 在我看来有两个选项可以生成递归方法：

首先，您可以 - 在第一次递归调用中 - 使用描述的方式遍历字符串，直到你是平衡的但是有一个剩余的字符串。然后你只需要在剩余的字符串上递归调用该方法。

因此，对于输入字符串 () [()]{([])}()[]，调用堆栈应变为：

isBalanced("()[()]{([])}()[]");
 isBalanced("[()]{([])}()[]");
  isBalanced("{([])}()[]");
   isBalanced("()[]");
     isBalanced("[]");

然而，这不会进入像 {([])} 这样的字符串的递归 - 因为它们可以在一次调用中处理。

第二种方法是根据 "characters" 进入递归。因此，您总是在一个递归调用中寻找第一个左括号的匹配括号 ，替换 both 并继续另一个调用。这将是一个较慢的解决方案 - 性能方面 - 但允许使用给定签名进行递归。

调用堆栈应该如下所示：

isBalanced("()[()]{([])}()[]"); isBalanced("__[()]{([])}()[]"); isBalanced("___()_{([])}()[]"); isBalanced("______{([])}()[]"); isBalanced("_______([])_()[]"); isBalanced("________[]__()[]"); isBalanced("____________()[]"); isBalanced("______________[]"); isBalanced("________________");

ps.: 不管你做什么，别忘了加

isBalanced(String str){ if (str.length() % 2 != 0) return false; ... }

对于 "A+" :-)

判断包含括号的字符串是否平衡

Determine if a string that contains parentheses is balanced

java

string

recursion