1、题目

编写一个 Stack 的用例 Parentheses,从标准输入中读取一个文本流并使用栈判定其中的括号是否配对完整。例如,对于 [()]{}{()()} 程序应该打印 true,对于 [(]) 则打印 false。

2、解析

利用栈的特性,左括号全部入栈,遇到右括号,马上出栈第一个元素,如果出栈元素和右括号匹配,则表示是一个完整的括号对,否则之间返回false。

额外需要注意的两个点:

  1. 右括号实际数量超标,类似于这种:[()]],对于这种case,循环遇到右括号时候,判断栈是否为空。
  2. 左括号实际数量超标,类似于这种:[[()],对于这种case,整体循环完毕后,判断栈是否为空。

3、程序

package kb.algorithm;

public class Parentheses {

    public static void main(String[] args) {
        String s = "[[[[[]]]";
        System.out.println(isMatched(s));
    }

    public static boolean isMatched(String s) {
        Stack<Character> items = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character item = s.charAt(i);
            if (item == '(' || item == '{' || item == '[') {
                items.push(item);
            }
            if (item == ')') {
                if (items.empty()) {
                    return false;
                }
                Character pop = items.pop();
                if (pop != '(') {
                    return false;
                }
            }
            if (item == '}') {
                if (items.empty()) {
                    return false;
                }
                Character pop = items.pop();
                if (pop != '{') {
                    return false;
                }
            }
            if (item == ']') {
                if (items.empty()) {
                    return false;
                }
                Character pop = items.pop();
                if (pop != '[') {
                    return false;
                }
            }
        }
        if (items.empty()) {
            return true;
        } else {
            return false;
        }
    }
}

内容来源于网络如有侵权请私信删除