有效的括号---2022/02/23

题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
题目来源

解题思路

思路：
利用栈的知识，后进先出来进行判断
如果是左括号，压入栈中；
如果是右括号，判断最顶上的左括号是否匹配，如果匹配直接出栈，否则返回false；字符遍历结束之后，且栈中没有不存在元素，则返回true。这里的思考是，如何来构造栈，并使用相应的操作来实现出栈与入栈

收获：
1、J ava中的栈类：引入包Stack
2、用栈Stack 创建对象（类型不同）
Stack stack = new Stack<>();
Stack stack = new Stack<>();
3、考虑两种特殊情况，如果左括号先入找不到匹配的情况：此时要判断
所有的右括号都匹配之后，栈里面是否还存在元素；如果前面的括号
以及完成匹配，后入的右括号如何发现无法匹配信息，此时就需要检
查此时栈中是否有元素存在。
4、如果输入为空的情况， 拓展：栈类对于需要先进后出的情况使用，比如括号的判断，表达式的求解等。

代码实现

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;

    }

}

性能评估与分析

平台上提交的方法性能并不高，这是因为调用系统函数会比自己写的函数实现更费时。不过也当熟练一下如何调用库函数吧。