用自定義鏈式堆疊解決力扣括號匹配問題

• 一、背景
• 二、解題思路
• 三、編碼實作
  • 1、結點
  • 2、鏈式堆疊
  • 3、用鏈式堆疊實作括號匹配的判斷
• 四、代碼執行
  • 測驗1
  • 測驗2
  • 測驗3
  • 空字串測驗

一、背景

在力扣題庫中有一道經典的堆疊表應用問題：有效的括號

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串，判斷字串是否有效，
有效字串需滿足：
1、 左括號必須用相同型別的右括號閉合，
2、左括號必須以正確的順序閉合，
3、注意空字串可被認為是有效字串，
來源：力扣（LeetCode）
鏈接：https://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 = https://www.cnblogs.com/zhuhuix/p/t;
        this.next = n;
    }

    public T getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node 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 = https://www.cnblogs.com/zhuhuix/p/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）
 * 鏈接：https://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

空字串測驗

標籤：Java

上一篇：資料分析 | 基于智能標簽，精準管理資料

下一篇：JAVA自學筆記（4）