java - 递归检查字符串是否平衡

Question

我想检查一个字符串是否有匹配的大括号、方括号或圆括号。

For example:
{}
()
[]

我可以用堆栈来做。我想用递归来做。我正在阅读一个类似问题的答案，答案是递归和堆栈的混合。一位用户回复了这些答案说递归也是一个堆栈，因此您的递归方法不应该在参数中有一个堆栈——这对我来说很有意义。

但我有一个大问题，我正在向后查看字符串并始终删除我检查的最后一个位置，直到字符串为空，所以我返回 true。如果我的方法中没有额外的参数来保存我要查找的内容，我无法想象我将如何检查特定部分、大括号、方括号或圆括号。但我一直认为必须有一种更简单的方法来做到这一点。

public boolean isBalanced(String in)
{
    if(in.isEmpty())
        return true;

    if(in.charAt(in.length()) == '}')
    {
        return recIsBalanced(in.substring(0, in.length()));
    }

    else if(in.charAt(in.length()) == ']')
    {

    }


    return recIsBalanced(in.substring(0, in.length()));
}

Answer 1

使用递归解决此问题的最简单方法是从两个方向收缩字符串。您从左到右迭代，直到看到 。如果这些不匹配，则字符串不平衡，否则对包含在这些大括号之间的字符串应用相同的算法。仅从一端开始会更加棘手，您将不得不存储一些状态。

编辑:感谢 DanielFischer。实际上从一侧迭代，例如左移直到找到一个大括号(如果这个大括号没有打开一个返回 false)。比从另一边迭代(在这种情况下是正确的)直到找到匹配的大括号。现在，当且仅当包含在大括号内的子字符串是平衡的和右括号右侧的字符串都使用递归平衡时，字符串才会平衡。