数据结构笔记总结(2.3)栈的另一个应用:括号匹配

栈的应用举例

  • Undo操作-编辑器
  • 系统调用栈-操作系统
  • 括号匹配-编译器

20.Valid Parentheses

有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效(正确匹配)。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

示例 2:

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

示例 3:

输入: “(]”
输出: false

示例 4:

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

示例 5:

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

解决思路

面对这样一个字符串,我们可以先声明一个栈,之后可以逐一的遍历这个字符串中的每一个字符

如果这个字符是一个左括号(不管是大括号、小括号还是中括号)我们就把它压入栈

第一个字符是左侧大括号,将它压入栈,第二个字符是左侧中括号,将它压入栈,第三个字符是左侧小括号,也压入栈。

当前字符是右侧的小括号了,看一下栈顶元素是不是左侧的小括号,发现是左侧小括号,这个就匹配成功了,相应的左侧小括号就可以出栈了,

同理,后两个也匹配了,都出栈,此时栈为空,说明我们这个是个合法的匹配的字符串。

接下来,看一个反例,如下是一个错误的不匹配的字符串

[v_notice]在这个算法中,栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素[/v_notice]

代码演示

我们先使用java的util的类来实现

import java.util.Stack;

class Solution {

    public boolean isValid(String s) {

        Stack 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())
                    return false;

                char topChar = stack.pop();
                if(c == ')' && topChar != '(')
                    return false;
                if(c == ']' && topChar != '[')
                    return false;
                if(c == '}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(2.3)栈的另一个应用:括号匹配

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多