Suppose two parentheses are allowed in an expression , parentheses & square brackets , Its nesting order is random , Namely [()[]],[([][])] and []()[] Etc. is the correct format ,[(]) or ([())
Etc. are not in the correct format . It is required to write a program to check whether the bracket input is correct .

<> Realization ideas

We use the last in, first out principle of stack to realize this problem , The idea is as follows :

* If ] or ) At the beginning, the brackets must not match .
* Split the received string into single characters
* Traverse to stack
* If the current stack is empty , Then directly into the stack
* If the current stack is not empty , Then take the stack top data and compare it with the current data . If two brackets match , Then take out the stack top data . Otherwise, stack the current data
* Check whether the stack is empty after traversal . If it is blank, the verification is successful , Otherwise, the inspection fails

<> code implementation
package com.codestd.study.stack; import java.util.Stack; /** * Bracket check * @author
jaune * @since 1.0.0 */ public class BracketChecker { /** * Check whether the brackets are correct * @param
in Enter bracket string */ public static boolean check(String in) { char[] chars = in.
toCharArray(); Stack<Character> stack = new Stack<>(); for (char aChar : chars)
{ // Discard directly if it is not bracket character if (isBracket(aChar)) { if (stack.isEmpty()) { stack.push(
aChar); } else { char stackChar = stack.peek(); //
Pay attention to the order here , It must be a parenthesis in the stack , Compared with parentheses . Order cannot be disordered .)( This format is wrong . if (checkPairBracket(stackChar,
aChar)) { stack.pop(); } else { stack.push(aChar); } } } } return stack.isEmpty(
); } /** * Verify that the front and back brackets match * @param ch1 Parenthesis * @param ch2 Parenthesis */ public static
boolean checkPairBracket(char ch1, char ch2) { return ch1 == '(' && ch2 == ')'
|| ch1 == '[' && ch2 == ']'; } /** * Check whether it is bracket character */ public static boolean
isBracket(char ch) { return ch == '(' || ch == ')' || ch == '[' || ch == ']'; }
}
There are only parentheses and brackets in this question , If you add braces , Or book name and other characters in pairs , The core code does not need to be modified , Only need to modify checkPairBracket and isBracket
that will do . No matter how many brackets , The principle of verification is the same .

The test code is as follows :
import static org.assertj.core.api.Assertions.*; /** * Test for {@link
BracketChecker} */ public class BracketCheckerTest { @Test public void test() {
String s1= "[]()[(())()]"; assertThat(BracketChecker.check(s1)).isTrue();
String s2= ")[]()[]"; assertThat(BracketChecker.check(s2)).isFalse(); String s3
= "[(])[]"; assertThat(BracketChecker.check(s3)).isFalse(); } }
The above test code has passed the test . Because the underlying implementation of the stack is array or linked list , So using arrays can also solve this problem . You only need a pointer to the end of the array .

Technology
©2019-2020 Toolsou All rights reserved,
html Writing about cherry trees , Writing about cherry trees It's unexpected Python Cherry tree (turtle The gorgeous style of Library ) Browser kernel ( understand )HashMap Explain in detail java Four functional interfaces ( a key , simple )os Simple use of module Some East 14 Pay change 16 salary , Sincerity or routine ?