括号匹配问题流程图_带星号的括号匹配

括号匹配问题流程图_带星号的括号匹配文章目录前言例题算法思想算法举例代码栈类括号匹配核心算法完整代码运行结果前言括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现

前言

括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现。最近刷题的时候也遇到了,就想写一篇文章整理一下。

例题

题目来自Leetcode中国
给定一个只包括 (){
}[] 的字符串,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:

输入: “()”
输出: true

示例 2:

输入: “()[]{}”
输出: true

示例 3:

输入: “(]”
输出: false

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

算法思想

S1:遍历输入的括号序列,如果是左括号,进入S2,如果是右括号,进入S3
S2:如果当前遍历到左括号,则入栈
S3:如果当前遍历到右括号,则出栈一个元素,看其是否与当前的右括号组成一对,如果不是,则匹配失败。或者在出栈过程中发生异常(从空栈中出栈),也匹配失败
S4:若能顺利遍历完成,检查栈中是否还有剩余元素,如果有,则匹配失败;如果没有,则匹配成功。

算法举例

下面以(({[]}) 序列为例说明算法过程:
1、首先将这个字符串转换成字符数组,并初始化一个空栈。
括号匹配问题流程图_带星号的括号匹配
2、遍历到第0个元素,(,为左括号,入栈
括号匹配问题流程图_带星号的括号匹配
3、后面以此类推,遍历完第3个元素[后,栈空间应该是这样的
括号匹配问题流程图_带星号的括号匹配
4、遍历到第4个元素]时,发现为右括号,此时,从栈顶出栈一个左括号,即[,刚好[],匹配成一对
括号匹配问题流程图_带星号的括号匹配
5、以此类推,直到第6个元素),都是匹配的
括号匹配问题流程图_带星号的括号匹配
6、此时,序列已经遍历完毕,但是栈不是空的,所以原序列匹配失败。

代码

栈类

这里我使用了链栈,链表就没有自己写了,用了Java现成的LinkedList<T>

/** * 栈类,这里使用链栈 */
class MyStack{ 
   
    private int num;
    private LinkedList<Character> data;

    public MyStack(){ 
   
        this.num = 0;
        data = new LinkedList<Character>();
    }

    /** * 判断栈是否为空 * @return */
    public boolean isEmpty(){ 
   
        return num == 0 ? true : false;
    }

    /** * 入栈 * @param ch */
    public void push(Character ch){ 
   
        this.data.add(ch);
        this.num++;
    }

    /** * 出栈 * @return */
    public Character pop(){ 
   
    	 //栈为空时,返回' '
        if(this.isEmpty()){ 
   
            return ' ';
        }
        Character ch = this.data.remove(data.size()-1);
        this.num--;
        return ch;
    }
}

括号匹配核心算法

    /** * 核心方法 * @param s * @return */
    public boolean isValid(String s) { 
   
        char[] temp = s.toCharArray();
        MyStack stack = new MyStack();
        boolean flag = true;
        for(int i = 0 ; i < temp.length ; i++){ 
   
            //左括号,入栈
            if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){ 
   
                stack.push(temp[i]);
            }
            else{ 
   
                //右括号,出栈
                char left = stack.pop();
                //如果从栈中取出空值,说明栈已空,但还有右括号存在,肯定不匹配
                if(left == ' ') { 
   
                    flag = false;
                }
                //如果左右括号不匹配,则失败
                if(!check(left,temp[i])){ 
   
                    flag = false;
                }
            }
        }
        //循环完毕后,若栈不空,说明左括号个数大于右括号,不匹配
        if(flag){ 
   
            if(!stack.isEmpty()){ 
   
                flag = false;
            }
        }
        return flag;
    }
}

完整代码

import java.util.LinkedList;

/** * 括号匹配问题(Blog) */

/** * 栈类,这里使用链栈 */
class MyStack{ 
   
    private int num;
    private LinkedList<Character> data;

    public MyStack(){ 
   
        this.num = 0;
        data = new LinkedList<Character>();
    }

    /** * 判断栈是否为空 * @return */
    public boolean isEmpty(){ 
   
        return num == 0 ? true : false;
    }

    /** * 入栈 * @param ch */
    public void push(Character ch){ 
   
        this.data.add(ch);
        this.num++;
    }

    /** * 出栈 * @return */
    public Character pop(){ 
   
        //栈为空时,返回' '
        if(this.isEmpty()){ 
   
            return ' ';
        }
        Character ch = this.data.remove(data.size()-1);
        this.num--;
        return ch;
    }
}

class Solution { 
   

    /** * 判定左右括号是否匹配 * @param left * @param right * @return */
    private boolean check(char left , char right){ 
   
        if(left == '('){ 
   
            return right == ')' ? true : false;
        }

        if(left == '['){ 
   
            return right == ']' ? true : false;
        }

        if(left == '{'){ 
   
            return right == '}' ? true : false;
        }
        return false;
    }

    /** * 核心方法 * @param s * @return */
    public boolean isValid(String s) { 
   
        char[] temp = s.toCharArray();
        MyStack stack = new MyStack();
        boolean flag = true;
        for(int i = 0 ; i < temp.length ; i++){ 
   
            //左括号,入栈
            if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){ 
   
                stack.push(temp[i]);
            }
            else{ 
   
                //右括号,出栈
                char left = stack.pop();
                //如果从栈中取出空值,说明栈已空,但还有右括号存在,肯定不匹配
                if(left == ' ') { 
   
                    flag = false;
                }
                //如果左右括号不匹配,则失败
                if(!check(left,temp[i])){ 
   
                    flag = false;
                }
            }
        }
        //循环完毕后,若栈不空,说明左括号个数大于右括号,不匹配
        if(flag){ 
   
            if(!stack.isEmpty()){ 
   
                flag = false;
            }
        }
        return flag;
    }
}

public class Main { 
   

    public static void main(String[] args) { 
   
	// write your code here
        Solution solution = new Solution();
        System.out.println(solution.isValid("(({[]})"));
    }
}

运行结果

(({[]})的运行结果

false
Process finished with exit code 0

与我们之前预测的一致。

今天的文章括号匹配问题流程图_带星号的括号匹配分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/71099.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注