Valid parentheses ---2022/02/23

Title Description

Given one only includes ‘(’,’)’,’{’,’}’,’[’,’]’ String s , Determines whether the string is valid .
Valid string needs to meet ：
Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .
Title source

Their thinking

Ideas ：
Using stack knowledge , Last in, first out
If it's left parenthesis , Pressure into the stack ;
If it's right bracket , Determine whether the top left bracket matches , If it matches, it will be directly out of the stack , Otherwise return to false; After character traversal , And there are no non-existent elements in the stack , Then return to true. The thinking here is , How to construct a stack , And use the corresponding operations to achieve the stack and stack

Harvest ：
1、J ava Stack class in ： Introduction package Stack
2、 With the stack Stack Create objects （ Different types ）
Stack stack = new Stack<>();
Stack stack = new Stack<>();
3、 Consider two special cases , If the left parenthesis is entered first and no match is found ： At this point, judge
After all the closing parentheses match , Whether there are still elements in the stack ; If the preceding parentheses
And complete the matching , How does the last closing parenthesis find unmatched information , At this point, it is necessary to check
Check whether there are any elements in the stack at this time .
4、 If the input is empty , expand ： The stack class is used in the case of first in and last out , For example, the judgment of brackets , Expression solving, etc .

Code implementation

import java.util.Stack;	
public class IsValid_0223 {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		String str="{]";
		System.out.println(isValid(str));
	}
	
    public static boolean isValid(String s) {
    
    	Stack<Character> st=new Stack<>();
    	for(int i=0;i<s.length();i++)
    	{
    
    		if(s.charAt(i)=='{'|s.charAt(i)=='['|s.charAt(i)=='(') {
    
    			st.push(s.charAt(i));
    		}
    		else {
    
    			if(st.empty())
    			{
    
    				return false;
    			}
    			char te=st.pop();
    			switch(s.charAt(i)) {
    
	    			case '}':
	    					if(te=='{') {
    
	    						break;}
	    					else{
    
	    						return false;}
	    			case ']':
		    				if(te=='[') {
    
	    						break;}
	    					else{
    
	    						return false;}
	    			case ')':
		    				if(te=='(') {
    
	    						break;}
	    					else{
    
	    						return false;}
    			}
    			
    		}
    	}
    	if(st.isEmpty()) return true;
		return false;

    }

}

Performance evaluation and analysis

The performance of methods submitted on the platform is not high , This is because calling system functions is more time-consuming than implementing functions written by yourself . However, you should be familiar with how to call library functions .