引言{有效括号-->点击详细描述}
相信没有学习过数据结构的朋友们也一定会首先想到遍历的方式来解决这个问题，基本思路没有错但是我们似乎无法进行下一步了。这里我给大家提出几个问题也许能为大家打开思路：
- 我们如何解决小括号，中括号、大括号的条件判断？
2.如何解决各种特殊情况：
如:
( } （] [ } { ] -->无有效括号
( ] ] (}]） ……
简单来说就是如何通过条件从首位开始判断一个括号然后对比与其他括号，从而判断这个括号是否有效。这也就导致了我们每次必须保证其他括号不变，然后只能判断一个括号是否有效，所以我们的遍历思想只能运用于括号类型的判断，如果要判断是否有效，如果继续使用遍历判断我们就会发现我们并不能实现：
首先，遍历判断括号是否有效，必须进行回文进行检测，因为如果出现} ] ) 的话我们还要重新回去寻找另一半，这样显然效率是不高的，所以我们要另辟蹊径
3.我们如何解决没有有效括号的特殊情况？
下面我们正式开始我们的解答
方法：遍历为主体
首先我们先将遍历的框架搭起来
- 遍历主体
class Solution {
public boolean isValid(String s) {
char text;
for(int i;i<s.length();i++)
{
text=s.charAt(i);
}
}
这里我们从两个方面进行有效括号判断：
- 通过栈进行封装式判断、并且进行条件判断
class Solution {
public boolean isValid(String s) {
Stack<Character> stack=new Stack<>();//创建栈空间
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c=='('||c=='['||c=='{')
{
stack.push(c);
}
else if(stack.isEmpty()||c==')'&&stack.pop()!='('||c==']'&&stack.pop()!='['||c=='}'&&stack.pop()!='{')
{return false;}
}
return stack.isEmpty();
}
}
这种做法十分适合新手来进行理解，首先我们先从实验的角度解释什么是栈。
- 栈
所谓栈，可以理解为一种只有单口的试管，我们向里面填充同样口径的棉花糖，依次是红色、黄色、绿色，这样如果我们要取出这些棉花糖就必须要按绿色、黄色、红色的顺序取出。这里我们做一个小实验检测stack的使用方式。
public class Text10 {
public static void main(String[] args) {
Stack<Character> stack=new Stack<>();//创建栈空间
stack.push('a');
stack.push('b');
stack.push('c');//按a,b,c顺序输入
for(int i=0;i<=stack.size();i++)
{
System.out.println(stack.pop()+"\t"+stack.isEmpty()+"\t"+stack.size());
if(stack.pop()!=null||stack.isEmpty())
{
System.out.print(stack.pop());
}
}
}
}
运行结果:
通过结果我们发现本应该输出的b这时却消失了：这时因为当我们使用stack.pop()进行条件判断时我们已经无法再输出b,因为我们已经将它弹出，当我们进行下一步循环时栈里面就只有a了，当我们将它弹出后对于isempty()的判断当然只有true。这其实是pop()方法为了防止操作者出现越栈的情况，所以直接使用pop()方法只能输出倒数二个，而不能将栈每个数据输出，但我们可以通过如下方法将每一个数据输出。
stack.push('a');
stack.push('b');
stack.push('c');//按a,b,c顺序输入
for(int i=0;i<stack.size();i++)
{
System.out.println(stack.pop());
if(stack.size()==1)
{
System.out.println(stack.pop());
}
}
}
运行结果：
通过条件判断我们便能输出所有数据，但是针对于有效括号来说，最后一个括号肯定无法单独构成有效的。
通过解释栈的使用方法，我们便能更加理解这个方法的工作方式。
- 通过从字符串抽取一个字符，然后进行条件判断它的形态，如果为左半边括号，则将它推入栈空间中进行隔离，如果是右半边括号，则将它现有库中的左括号进行对比，找出匹配的括号。
现在我们单独将条件判断方式抽离出来：
if((stack.isEmpty())||(c==')'&&(stack.pop()!='(')||(c==']'&&(stack.pop()!='['))||(c=='}'&&stack.pop()!='{')){return false;}
这里的判断顺序是stack.isEmpty()--> c==')'&&(stack.pop()!='(' -->c==']'&&(stack.pop()!='['--> c=='}'&&stack.pop()!='{' 并且按照顺序只要实现一个就会让这个正确并返回false，不会进行后面的弹出，此时正确的左括号会被弹出。
这里用到的道理其实与消消乐一样，但是这是从小到大开始消除
我们先从小的字符串开始验算:
- () 首先将左括号进行输入，然后判断字符右括号是否为正确
[ ] 首先将‘[’读入栈中，然后判断右边是否为')'显然不是，但是这是']'已经在第一步判断弹出，然后判断‘]’成立，此时栈里面没有东西，所以第三部条件判断成立。所以正确。
然后我们稍微增加一个括号： - ()) 前面判断与第一个一样，然后判断第三个字符，发现栈空间不存在字符所以stack.isEmpty(）为true,所以显然返回错误,同理其他类型
- [() 此时栈里面储存了两个数据，判断条件时发现所有的都不成立,所以直接弹出，这时判断栈里面是否还含有数据，这时还剩下一个所以错误。
-[[) 这时储存两个数据，判断所有条件不成立
为了严谨我们在加两个：
- [()} 首先存入两个数据然后判断，这个跟加一个括号的第二个相同。
……
那么我们为什么要加入isempty()呢？ - 首先我们要知道，右括号左边是不能超过3个的因为如果多出一个，就算前面三个合适也会一定会与当前判断的字符发生冲突。
- 第二防止第一个字符就为右括号。
总结：
合理使用栈结构可以让判断对象能够更加高效，逻辑更加连贯。
