# Using custom chain stack to solve the problem of bracket matching

#### 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

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
*/
// Stack top element
private Node<T> top;
// Length of stack
private Integer length;

// Construction method
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
*
* @author zhuhuix
* @date 2020-05-30
*/
public static void main(String[] args) throws IOException {
System.out.println("Please enter only '('，')'，'{'，'}'，'['，']' String of");
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) {
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

##### Empty string test

Tags: Java

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