正则表达式可以找到平衡的括号模式吗？

Question

我在Java的一次采访中被问到这个问题。我不能解决它，但我猜它可以解决使用正则表达式。不确定是否有一种不使用正则表达式的替代方法。有人能帮我用正则表达式吗？或者，如果不使用正则表达式就能解决这个问题。

给定一个平衡括号字符串（它只包含[或]，并且它已经平衡），我需要查找它内部是否包含模式[*][*][*](*表示一个或多个平衡括号表达式）。也就是说，检查它是否在任何[]中包含3个或更多的[]。

示例：

对于[[][[][][]]],预期答案为true,因为其内部包含[][][]。

对于[[]][[]]预期答案为false，因为它的连续[]少于3个

对于[[]][][[]]],预期答案为true,因为其内部包含[..][][..]。如果[]内部有0个或更多的[]则无关紧要。

Answer 1

正则表达式不是解决这类问题的方法。由于递归，它们不能特别好地处理嵌套结构。

例如，对于使用堆栈(FILO)来说，这是一个完美的问题。我建议你看看那些。

class Node
{
    private final Node parent;
    private final List<Node> subNodes = new LinkedList<>();

    Node(Node parent)
    {
        this.parent = parent;
    }

    static Node buildFrom(String str)
    {
        Node start = new Node(null);
        Node current = start;

        for (char ch : str.toCharArray())
        {
            if (ch == '[') //Create new subnode
            {
                Node newNode = new Node(current);
                current.subNodes.add(newNode);
                current = newNode;
            }
            else //Step back
            {
                current = current.parent;
            }
        }
        return start;
    }

    boolean hasTripleNodes()
    {
        if (this.subNodes.size() >= 3) //Found triple+ nodes
        {
            return true;
        }
        else //Continue recursion
        {
            for (Node subNode: this.subNodes)
            {
                if (subNode.hasTripleNodes())
                {
                    return true;
                }
            }
            return false;
        }
    }

    //DEMO
    public static void main(String[] args) throws Exception {
        Node nodes = Node.buildFrom("[[][[][][]]]");
        System.out.println(nodes.hasTripleNodes()); //writes true

        nodes = Node.buildFrom("[[]][[][]]");
        System.out.println(nodes.hasTripleNodes()); //writes false

        nodes = Node.buildFrom("[[[]][][[]]]");
        System.out.println(nodes.hasTripleNodes()); //writes true
    }
}