美文网首页
算法分享第5题

算法分享第5题

作者: DevWang | 来源:发表于2017-12-22 22:23 被阅读0次
题目:Given a string containing just the characters '(',')','{','}','[' and ']', determine if the input string a valid.
the brackets must close in the correct order.
如:'()' and "()[]{}" are all valid but "(]" and "([)]" are not.




















思路:

  • 首先想到的便是使用栈的进出栈来匹配,当发现左括号时进栈,右括号时进行判断;
  • 如果栈顶元素为该右括号对应的左括号,则该元素出栈,否则返回不匹配;
  • 如果进出栈都无误,则在程序结束后检查栈中是否还有元素,无元素则返回匹配,有元素则返回不匹配.
匹配成功 - ()[]{} 匹配失败 - ([)]

代码:

private boolean match(String str) {
    int length = str.length();
    Stack stack = new Stack();
    for (int index = 0; index < length; index++) {
        char ch = str.charAt(index);
        switch (ch) {
            case '(':
            case '{':
            case '[':
                // 左括号进栈
                stack.push(ch);
                break;
            case ')':
                // 右括号 栈为空 返回false
                if (stack.empty()) {
                    return false;
                // 右括号 栈顶元素不是对应左括号返回false
                } else if ('(' != (char) stack.pop()) {
                    return false;
                }
                break;
            case '}':
                if (stack.empty()) {
                    return false;
                } else if ('{' != (char) stack.pop()) {
                    return false;
                }
                break;
            case ']':
                if (stack.empty()) {
                    return false;
                } else if ('[' != (char) stack.pop()) {
                    return false;
                }
                break;
            default:
                break;
        }
    }
    // 字符串遍历结束后栈为空则代表所有括号匹配成功
    return stack.empty();
}

相关文章

  • 算法分享第5题

    题目:Given a string containing just the characters '(',')',...

  • 算法分享第6题

    题目:用两个栈实现一个队列,只要求实现入队,出队方法即可. 假设这两个栈分别为s1,s2 分析思路1、栈的特性为:...

  • 算法分享第3题

    题目:给定两个整数a和b,交换这两个数字,要求不引入第三个变量 如:定义a=1、b=2 交换后 a=2、b=1 思...

  • 算法分享第4题

    题目:给定一串链表和一个整数n,要求删除链表倒数第n个节点 (注:输入的n永远是合法的,试着访问 '一次' 链表就...

  • 算法分享第1题

    题目:要求定义一个方法,实现对传入的字符串进行反转并返回 如:传入字符串ABCDEFG -> 返回GFEDCBA ...

  • 算法分享第2题

    题目:斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、…… 现在要求...

  • 习题集锦1.0

    第1题 第2题 第3题 第4题 第5题

  • 10道前端基础题

    第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第10题

  • 2017年“视界窗教学服务培训”调查问卷统计分析

    第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第10题

  • 周末作业题

    第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第10题 第11题 第12题 第13题 第...

网友评论

      本文标题:算法分享第5题

      本文链接:https://www.haomeiwen.com/subject/ptutpxtx.html