描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例
提交的代码
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public boolean isValid(String s) {
//剪枝操作
if(s.length()%2==1)return false;
Deque<Character> stack=new LinkedList<>();
char curChar=0;
for(int i=0;i<s.length();i++){
curChar=s.charAt(i);
if(curChar=='('){
stack.push(')');
}else if(curChar=='['){
stack.push(']');
}else if(curChar=='{'){
stack.push('}');
}else if(stack.isEmpty()||stack.peek()!=curChar){
return false;
}else{
stack.pop();
}
}
return stack.isEmpty();
}
}
思想：
用栈的思想来解决此问题，当遇到第一个左括号的时候，左括号入栈并且“迫切”一个右括号来消融它，如果下一个正好是相应的右括号，那么左括号出栈；若下一个元素是另一个左括号，那么前一个左括号“迫切”找到另一个右括号消融就需要降优先级，当前左括号入栈；循环此动作，直到当前字符串遍历完毕并且栈空，返回true。
试想一下，如果左括号多了一个，那么最后的结果就是遍历结束但在栈中不为空，此时返回false；如果右括号多了一个，会出现消融左括号的时候，发现栈中并没有相应的左括号并且栈为空，此时返回false；如果此时栈不为空，但是遍历到一个右括号的时候，发现栈顶元素左括号并不和当前右括号匹配，此时返回false。