• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客笔记 Geekerstar 1年前 (2018-05-08) 511次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

栈的应用举例

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

20.Valid Parentheses

有效的括号

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

有效字符串需满足:

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

示例 1:

输入: “()”
输出: true

示例 2:

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

示例 3:

输入: “(]”
输出: false

示例 4:

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

示例 5:

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

解决思路

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

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

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

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

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

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

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

代码演示

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

import java.util.Stack;

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

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

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(2.3)栈的另一个应用:括号匹配
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00