用自定义链式栈解决力扣括号匹配问题

智慧zhuhuix

发布于 2020-08-14 16:21:59

5530

发布于 2020-08-14 16:21:59

一、背景

在力扣题库中有一道经典的栈表应用问题：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足： 1、左括号必须用相同类型的右括号闭合。 2、左括号必须以正确的顺序闭合。 3、注意空字符串可被认为是有效字符串。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-parentheses

示例1	示例 2	示例 3	示例 4	示例 5
输入: "()"	输入: "()[]{}"	输入: "(]"	输入: "([)]"	输入: "{[]}"
输出: true	输出: true	输出: false	输出: false	输出: true

二、解题思路

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，遍历完所有括号后 stack仍然为空，则认为字符串中的括号都完全匹配；
如果输入的字符串中有括号外的其它字符，则直接返回无效；
如果输入了空字符串，则不会产生入栈，栈仍然为空，也可返回有效。

三、编码实现

由于输入的字符串长度不定，并考虑自定义一个链式栈（无栈满问题，空间可扩充）进行编码实现。

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）
 * 链接：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();
    }
}