Using custom chain stack to solve the problem of bracket matching

catalog

1, Background

There is a classic stack table application problem in the power deduction question bank: valid brackets

Given a string that only includes' (',' '', '{', '}', '[', ']', determine whether the string is valid.
Valid string needs to meet:
1. The opening bracket must be closed with a closing bracket of the same type.
2. The left parenthesis must be closed in the correct order.
3. Note that empty strings can be considered valid strings.
Source: LeetCode
Link: https://leetcode-cn.com/problems/valid-parentheses

Example 1 Example 2 Example 3 Example 4 Example 5
Input: '()' Input: '() [] {}' Input: '(]' Input: '([)]' Type: '{[]}'
Output: true Output: true Output: false Output: false Output: true

2, Solutions to problems

  1. The stack first in and then out feature is exactly the same as the bracket sorting feature of this topic, that is, if the left bracket is found in the stack, when the right bracket is found, the left bracket at the top of the stack will be found out. After traversing all the brackets, the stack is still empty, then the brackets in the string are considered to match completely;
  2. If there are other characters outside the parentheses in the input string, the direct return is invalid;
  3. If an empty string is entered, no push is generated, the stack is still empty, and it can also return valid.

3, Coding implementation

Due to the indefinite length of the input string, a custom chain stack (no stack full problem, expandable space) is considered for coding.

1. Node

Each element, in addition to storing its own information (data domain), also needs to store a pointer indicating its direct storage location. These two parts of information constitute the storage image of data elements, which is called Node.

/**
 * Node class
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class Node<T> {
    // Data field
    private T data;
    // Pointer
    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. Chain stack
  • Chain stack is composed of N nodes;
  • Stack in and stack out are completed at the top of the stack;
  • The pointer from the node below the top of the stack links the next node to the end of the stack.
/**
 * The realization of chain stack
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class LinkStack<T> {
    // Stack top element
    private Node<T> top;
    // Length of stack
    private Integer length;

    // Construction method
    public LinkStack() {
        this.top = null;
        this.length = 0;
    }

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

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

    // View top of stack elements
    public T peek() {
        if (this.top == null) {
            return null;
        }
        T data = this.top.getData();
        return data;
    }

    // Is the stack empty
    public boolean isEmpty(){
        return this.length==0;
    }

    // Destroy stack
    public void destroy() {
        this.top =null;
        this.length = 0;
    }


    public Integer getLength() {
        return this.length;
    }
}
3. Using chain stack to judge bracket matching
/**
 * ==Using chain stack to solve the problem of bracket matching==
 * <p>
 * Given a string that only includes' (',' '', '{', '}', '[', ']', determine whether the string is valid.
 * Valid string needs to meet:
 * The opening bracket must be closed with a closing bracket of the same type.
 * The left parenthesis must be closed in the correct order.
 * Note that empty strings can be considered valid strings.
 * <p>
 * Source: LeetCode
 * Link: 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("Please enter only '(',')','{','}','[',']' String of");
        String s = bufferedReader.readLine();
        if (isValid(s)) {
            System.out.println("String parentheses match each other, valid");
        } else {
            System.out.println("Parentheses of string do not match, invalid");
        }
    }

    /**
     * Whether the brackets match is judged by the algorithm of putting the left bracket into the stack and putting the right bracket out of the stack
     *
     * @param s String to be judged
     * @return false for mismatch, true for match
     */
    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) {
                // Left bracket in stack
                case "(":
                case "[":
                case "{":
                    stack.push(ch);
                    break;
                case ")":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // If the top of the stack is left bracket, the stack will be matched
                    if ("(".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                case "]":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // If the top of the stack is left bracket, the stack will be matched
                    if ("[".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                case "}":
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // If the top of the stack is left brace, the stack will be matched
                    if ("{".equals(stack.peek())) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                default:
                    return false;

            }
        }
        return stack.isEmpty();
    }
}

4, Code execution

Test 1

Test 2

Test 3

Empty string test

Tags: Java

Posted on Fri, 29 May 2020 21:18:15 -0700 by vasilis