algs4 1.3.4 基于泛型的任意 "括号" 匹配校验算法

Parentheses.java

package life.yanfeng.study.algorithm;

import edu.princeton.cs.algs4.StdOut;

// for 1.3.4
public class Parentheses<Item> {
    private Bracket<Item>[] brackets;

    Parentheses(Bracket<Item>[] brackets) {
        this.brackets = brackets;
    }

    boolean isMatch(Item[] items) {
        Stack<Item> stack = new Stack<>();
        for (int i = 0; i < items.length; i++) {
            Item item = items[i];

            for (int j = 0; j < brackets.length; j++) {
                Bracket bracket = brackets[j];
                if (item.equals(bracket.right)) {
                    if (!stack.isEmpty() && stack.top().equals(bracket.left)) {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if(item.equals(bracket.left)) {
                    stack.push(item);
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Bracket<String>[] brackets = new Bracket[3];
        brackets[0] = new Bracket<>("(", ")");
        brackets[1] = new Bracket<>("[", "]");
        brackets[2] = new Bracket<>("{", "}");

        Parentheses checker = new Parentheses<String>(brackets);
        String[] todoChecks = {"[()]{}{[()()]()}", "[(])"};
        for (int i = 0; i < todoChecks.length; i++) {
            String item = todoChecks[i];
            if (checker.isMatch(item.split(""))) {
                StdOut.println(item + " is match");
            } else {
                StdOut.println(item + " is not match");
            }
        }
    }
}

// 括号.
class Bracket<Item> {
    Item left;
    Item right;

    Bracket(Item left, Item right) {
        this.left = left;
        this.right = right;
    }
}

[()]{}{()()} is match
[(]) is not match