【关于栈】Valid Parentheses详解

Valid parentheses问题详解

关于栈，我们就不得不说valid parentheses
这是一个关于讨论字符串合法性的问题：
如果括号成对嵌套，则合法
如果括号不成对嵌套，则非法
具体的步骤就是使用栈推入字符，然后在一半的时候，进行匹配，如果匹配，则出栈，继续匹配，如果不匹配，则终止匹配。
从这个问题可以看出，栈适合嵌套的层级关系的问题处理。
而栈顶元素代表了嵌套层级关系中，最近的需要匹配的元素。

那么，既然知道了，栈的适用范围，结合栈的基本属性我们就可以写流程以及代码了。

1. 首先我们要构造一个函数判断这个字符串是否有效，输入的值为字符串，输出的值为布尔值。

   public static boolean isValid(String s){
       
   }
   

2. 然后我们需要构造一个字符数组来存放切片的字符串，一个栈来存放我们需要判定的字符

       //设置一个转换字符数组
       char[] ch = s.toCharArray();
       //1.设置一个栈，且为泛型，只允许character通过
       Stack<Character> stack = new Stack<>();
   

3. 拿到数组并且切片之后，我们需要对字符进行判断，如果合法，就入栈，如果不合法，就进行下一步操作。

   //2.遍历数组中元素
       for(int i=0;i<s.length();i++){
           //3.如果匹配，则入栈
           if (ch[i]=='{' || ch[i]=='[' || ch[i]=='('){
               stack.push(ch[i]);
           }
           else{
             
               }
   

4. 如果不合法，也分为两种情况，第一种是没有一个字符匹配，整个字符串都是非法字符，就不会进栈，这时候直接返回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