用自定義鏈式棧解決力扣括弧匹配問題

• 2020 年 5 月 30 日
• 筆記
• JAVA, leetcode, 數據結構

一、背景

在力扣題庫中有一道經典的棧表應用問題：有效的括弧

給定一個只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字元串，判斷字元串是否有效。
有效字元串需滿足：
1、 左括弧必須用相同類型的右括弧閉合。
2、左括弧必須以正確的順序閉合。
3、注意空字元串可被認為是有效字元串。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/valid-parentheses

二、解題思路

1. 棧先入後出特點恰好與本題括弧排序特點一致，即若遇到左括弧入棧，遇到右括弧時將對應棧頂左括弧出棧，遍歷完所有括弧後 stack仍然為空，則認為字元串中的括弧都完全匹配；
2. 如果輸入的字元串中有括弧外的其它字元，則直接返回無效；
3. 如果輸入了空字元串，則不會產生入棧，棧仍然為空，也可返回有效。

三、編碼實現

由於輸入的字元串長度不定，並考慮自定義一個鏈式棧（無棧滿問題，空間可擴充）進行編碼實現。

1、結點

每個元素，除了存儲其本身的資訊（數據域）之外，還需存儲一個指示其直接後繼存放位置的指針。這兩部分資訊組成數據元素的存儲映像，稱為結點（Node）。

/**
 * 結點類
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class Node<T> {
    // 數據域
    private T data;
    // 指針
    private Node<T> next;

    Node(T t, Node<T> n) {
        this.data = t;
        this.next = n;
    }

    public T getData() {
        return data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

2、鏈式棧

• 鏈式棧是由N個結點組成的；
• 入棧出棧都在棧頂完成；
• 從棧頂以下的結點的指針鏈接下一個結點，直至棧尾。

/**
 * 鏈棧的實現
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class LinkStack<T> {
    // 棧頂元素
    private Node<T> top;
    // 棧的長度
    private Integer length;

    // 構造方法
    public LinkStack() {
        this.top = null;
        this.length = 0;
    }

    // 入棧push
    public void push(T t) {
        this.top = new Node<>(t, this.top);
        this.length++;
    }

    // 出棧pop
    public T pop() {
        if (this.top == null) {
            return null;
        }
        T data = this.top.getData();
        this.top = this.top.getNext();
        this.length--;
        return data;
    }

    // 查看棧頂元素
    public T peek() {
        if (this.top == null) {
            return null;
        }
        T data = this.top.getData();
        return data;
    }

    // 棧是否為空
    public boolean isEmpty(){
        return this.length==0;
    }

    // 銷毀棧
    public void destroy() {
        this.top =null;
        this.length = 0;
    }


    public Integer getLength() {
        return this.length;
    }
}

3、用鏈式棧實現括弧匹配的判斷

/**
 * ==用鏈式棧解決力扣括弧匹配問題==
 * <p>
 * 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。
 * 有效字元串需滿足：
 * 左括弧必須用相同類型的右括弧閉合。
 * 左括弧必須以正確的順序閉合。
 * 注意空字元串可被認為是有效字元串。
 * <p>
 * 來源：力扣（LeetCode）
 * 鏈接：//leetcode-cn.com/problems/valid-parentheses
 *
 * @author zhuhuix
 * @date 2020-05-30
 */
public class LinkStackTest {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("請輸入只包括 '('，')'，'{'，'}'，'['，']' 的字元串");
        String s = bufferedReader.readLine();
        if (isValid(s)) {
            System.out.println("字元串的括弧相互匹配，有效");
        } else {
            System.out.println("字元串的括弧不匹配，無效");
        }
    }

    /**
     * 通過左括弧入棧，右括弧出棧的演算法判斷括弧是否匹配
     *
     * @param s 待判斷的字元串
     * @return 不匹配返回false, 匹配返回true
     */
    public static boolean isValid(String s) {
        LinkStack<String> stack = new LinkStack<>();
        for (int i = 0; i < s.length(); i++) {
            String ch = s.substring(i, i + 1);
            switch (ch) {
                // 左括弧入棧
                case "(":
                case "[":
                case "{":
                    stack.push(ch);
                    break;
                case ")":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // 如果棧頂為左小括弧，則匹配出棧
                    if ("(".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                case "]":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // 如果棧頂為左中括弧，則匹配出棧
                    if ("[".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                case "}":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // 如果棧頂為左大括弧，則匹配出棧
                    if ("{".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                default:
                    return false;

            }
        }
        return stack.isEmpty();
    }
}

四、程式碼執行

測試1

測試2

測試3

空字元串測試