1.1.2 Stack: Brackets Matching

當想要檢驗一個輸入當中的括號順序跟種類是否正確, 可以透過stack來做檢查.

原始碼點我

package idv.carl.datastructures.stack;

/**
 * @author Carl Lu
 */
public class CheckBrackets {

    private final static char FORMER_PARENTHESES = '(';
    private final static char LATTER_PARENTHESES = ')';
    private final static char FORMER_BRACKET = '[';
    private final static char LATTER_BRACKET = ']';
    private final static char FORMER_BRACE = '{';
    private final static char LATTER_BRACE = '}';

    public boolean check(String input) {
        boolean match = true;
        Stack stack = new Stack(50);
        // Step1. Transform the string into char array
        char[] chars = input.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];

            if (isFormerPart(c)) {
                /*
                 * Step2. Read chars sequentially, push the char into stack
                 * if it's the former part of the brackets
                 */
                stack.push(c);
            } else if (isLatterPart(c)) {
                /*
                 * Step3. If encounter the latter part of the brackets,
                 * pop a value from stack and try to match
                 */
                char former = (char) stack.pop();
                if (misMatch(former, c)) {
                    System.out.println("Char mismatch, index at: " + (i + 1));
                    match = false;
                } else {
                    System.out.println("Char match.");
                    match = true;
                }
            }

        }
        return match;
    }

    private boolean isFormerPart(char c) {
        return (c == FORMER_PARENTHESES || c == FORMER_BRACKET || c == FORMER_BRACE);
    }

    private boolean isLatterPart(char c) {
        return (c == LATTER_PARENTHESES || c == LATTER_BRACKET || c == LATTER_BRACE);
    }

    private boolean misMatch(char former, char latter) {
        return ((former == FORMER_PARENTHESES && latter != LATTER_PARENTHESES)
                || (former == FORMER_BRACKET && latter != LATTER_BRACKET) || (former == FORMER_BRACE && latter != LATTER_BRACE));
    }

}