資料結構&演算法筆記
  • Introduction
  • 1. Data Structure
  • 1.1 Stack
  • 1.1.1 Stack: Revert String
  • 1.1.2 Stack: Brackets Matching
  • 1.1.3 Stack: Reverse Polish Notation
  • 1.1.4 Stack: Calculattion for Reverse Polish Notation
  • 1.2 Queue
  • 1.2.1 Priority Queue
  • 1.3 Linked List
  • 1.3.1 Linked List - Reorder Function
  • 1.3.2 Ordered Linked List
  • 1.4 Tree
  • 1.4.1 Binary Search Tree
  • 1.4.2 Heap Tree
  • 1.4.3 Red-Black Tree
  • 1.4.3.1 RB Tree Insertion
  • 1.4.3.2 RB Tree Insertion Implementation
  • 1.4.3.3 RB Tree Delete
  • 1.4.3.4 RB Tree Delete Implementation
  • 1.4.4 B-Tree
  • 2. Algorithm
  • 2.1 Sort
  • 2.1.1 Bubble Sort
  • 2.1.2 Selection Sort
  • 2.1.3 Insertion Sort
  • 2.1.4 Merge Sort
  • 2.1.5 Quick Sort
  • 2.1.6 Merge Sort v.s. Quick Sort
  • 2.2 Search
  • 2.2.1 Binary Search
  • 2.3 Dynamic Programming
  • 2.3.1 Fibonacci Series
  • 2.3.2 Find Longest Common Suffix
  • X. Time Complexity Cheat Sheet
Powered by GitBook
On this page

Was this helpful?

1.1.2 Stack: Brackets Matching

Previous1.1.1 Stack: Revert StringNext1.1.3 Stack: Reverse Polish Notation

Last updated 5 years ago

Was this helpful?

當想要檢驗一個輸入當中的括號順序跟種類是否正確, 可以透過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));
    }

}
點我