关于栈，我们就不得不说valid parentheses
这是一个关于讨论字符串合法性的问题：
如果括号成对嵌套，则合法
如果括号不成对嵌套，则非法
具体的步骤就是使用栈推入字符，然后在一半的时候，进行匹配，如果匹配，则出栈，继续匹配，如果不匹配，则终止匹配。
从这个问题可以看出，栈适合嵌套的层级关系的问题处理。
而栈顶元素代表了嵌套层级关系中，最近的需要匹配的元素。
那么，既然知道了，栈的适用范围，结合栈的基本属性我们就可以写流程以及代码了。
首先我们要构造一个函数判断这个字符串是否有效，输入的值为字符串，输出的值为布尔值。
我要评论public static boolean isValid(String s){
}
然后我们需要构造一个字符数组来存放切片的字符串，一个栈来存放我们需要判定的字符
//设置一个转换字符数组
char[] ch = s.toCharArray();
//1.设置一个栈，且为泛型，只允许character通过
Stack<Character> stack = new Stack<>();
拿到数组并且切片之后，我们需要对字符进行判断，如果合法，就入栈，如果不合法，就进行下一步操作。
//2.遍历数组中元素
for(int i=0;i<s.length();i++){
//3.如果匹配，则入栈
if (ch[i]=='{' || ch[i]=='[' || ch[i]=='('){
stack.push(ch[i]);
}
else{
}
如果不合法，也分为两种情况，第一种是没有一个字符匹配，整个字符串都是非法字符，就不会进栈，这时候直接返回false值就可以了。
//2.遍历数组中元素
for(int i=0;i<s.length();i++){
//3.如果匹配，则入栈
if (ch[i]=='{' || ch[i]=='[' || ch[i]=='('){
stack.push(ch[i]);
}
else{
//如果栈为空，则返回false
//说明一个都没有进去
if(stack.size() == 0){
return false;
}
另一种情况则是，字符进去了，后面的字符不匹配。这时候就要去取栈顶元素。如果栈顶元素不匹配，就返回false值，如果栈顶元素匹配，就出栈，继续取后面一个的栈顶元素。
//2.遍历数组中元素
for(int i=0;i<s.length();i++){
//3.如果匹配，则入栈
if (ch[i]=='{' || ch[i]=='[' || ch[i]=='('){
stack.push(ch[i]);
}
else{
//如果栈为空，则返回false
//说明一个都没有进去
if(stack.size() == 0){
return false;
}
//否则的话我们就可以拿到栈顶元素，取出栈顶元素
Character c = stack.peek();
//出栈
stack.pop();
//设置一个匹配的字符串
Character match;
if(ch[i] == ')'){
match ='(';
}
else if(ch[i]==']'){
match = '[';
}
else{
//查assert的用法
assert(ch[i]=='}');
match = '{';
}
//如果栈顶元素不匹配match，说明有问题
if(c!=match){
return false;
}
}
最后判断有没有出栈干净，如果没有出栈干净，说明一些字符无法和左括号匹配上（比如单纯只是[{[这样的字符串，也是非法的）则返回假。
有就返回真。
//没有出栈干净
if (stack.size() !=0)
{
return false;
}
//返回空值
return true;
代码如下：
public static boolean isValid(String s){
//设置一个转换字符数组
char[] ch = s.toCharArray();
//1.设置一个栈，且为泛型，只允许character通过
Stack<Character> stack = new Stack<>();
//2.遍历数组中元素
for(int i=0;i<s.length();i++){
//3.如果匹配，则入栈
if (ch[i]=='{' || ch[i]=='[' || ch[i]=='('){
stack.push(ch[i]);
}
else{
//如果栈为空，则返回false
//说明一个都没有进去
if(stack.size() == 0){
return false;
}
//否则的话我们就可以拿到栈顶元素，取出栈顶元素
Character c = stack.peek();
//出栈
stack.pop();
//设置一个匹配的字符串
Character match;
if(ch[i] == ')'){
match ='(';
}
else if(ch[i]==']'){
match = '[';
}
else{
//查assert的用法
assert(ch[i]=='}');
match = '{';
}
//如果栈顶元素不匹配match，说明有问题
if(c!=match){
return false;
}
}
}
//如果不匹配的话
//没有出栈干净
if (stack.size() !=0)
{
return false;
}
//返回空值
return true;
}
具体过程图示：
测试主函数
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Please input a string:");
String s = input.next();
System.out.println(isValid(s));
}
测试结果：
谢谢大家
本文地址：https://blog.csdn.net/weixin_43619860/article/details/107082184
如对本文有疑问， 点击进行留言回复！！
【java基础】面试常见问题：类和对象，封装继承多态，final关键字，static关键字，类加载过程，双亲委派模型
荐 Java语言基础之JDK1.8新特性（Lambda表达式、函数式接口、Stream流、新的日期API）
网友评论