括号配对问题

括号配对问题

Overview

括号配对问题是一道非常经典的ACM试题，当我第一次接触到这次个题目的时候，一直没能够写出答案。今天在学习堆栈结构的是否受到《啊哈，算法》这本书的启发，重新研究了一下这道题，终于是得到了一个解决方案。

最初解法

首先定义一个简单的堆栈的数据结构

public class MyStack {
    char[] mCharArray = new char[100];
    private int mTop;
    private int mLen;

    public void push(char c) {
        mCharArray[mTop++] = c;
        mLen++;
    }

    public char pop() {
        mLen--;
        return mCharArray[--mTop];
    }

    public int getLength() {
        return mLen;
    }
}

然后利用写好的堆栈结构进行解题

public class Program {

    public static void main(String[] args) {
        //String str = "[{{}((()()))}]";
//        String str = "()[]{}";
//        String str = "[[]()({)}]";
        String str = "[[]()(){]}";
        MyStack stackA = new MyStack();
        MyStack stackB = new MyStack();
        int count = str.length();
        if (count % 2 != 0) {
            System.out.println("NO");
            return;
        }
        for (int i = 0; i < str.length() - 1; i++) {
            if (count <= 0) {
                break;
            }
            //如果相邻的括号是匹配的话直接入栈
            if (isMatched(str.charAt(i), str.charAt(i + 1))) {
                stackA.push(str.charAt(i));
                stackB.push(str.charAt(i + 1));
                count -= 2;
                i += 1;
            } else {//否则将取最远处向对应的那个括号入栈
                stackA.push(str.charAt(i));
                stackB.push(str.charAt(i + count - 1));
                count -= 2;
            }
        }

        while (stackA.getLength() > 0) {
            if (!isMatched(stackA.pop(), stackB.pop())) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    private static boolean isMatched(char a, char b) {
        return (a == '(' && b == ')') || (a == '{' && b == '}') || (a == '[' && b == ']');
    }
}

测试数据	结果
[{{}((()()))}]	YES
()[]{}	YES
[({)}]	NO
[(){]}	NO

改善后的解法

当写完上面的解法后，发现堆栈数据结构并不是必需品，所以，移除对堆栈的应用。代码如下

public static void main(String[] args) {
    String str = "[{{}((()()))}]";
    //String str = "()[]{}";
    //String str = "[[]()({)}]";
    //String str = "[[]()(){]}";
    MyStack stackA = new MyStack();
    MyStack stackB = new MyStack();
    int count = str.length();
    if (count % 2 != 0) {
        System.out.println("NO");
        return;
    }
    for (int i = 0; i < str.length() - 1; i++) {
        if (count <= 0) {
            break;
        }
        //判断相邻的括号
        if (isMatched(str.charAt(i), str.charAt(i + 1))) {
            count -= 2;
            i += 1;
        } else if (isMatched(str.charAt(i), str.charAt(i + count - 1))) {//判断相对应的括号
            count -= 2;
        } else {
            System.out.println("NO");
            return;
        }
    }
    System.out.println("YES");
}

private static boolean isMatched(char a, char b) {
    return (a == '(' && b == ')') || (a == '{' && b == '}') || (a == '[' && b == ']');
}

测试数据	结果
[{{}((()()))}]	YES
()[]{}	YES
[({)}]	NO
[(){]}	NO

整体思路

1. 判断相邻的两个括号是否是匹配的
2. 如果相邻的两个括号不匹配，那么判断相对(比如: [{{{}}}] 这组括号序列 第一个 [ 和 最后一个 ] 是相对的)的连个括号组合是否是相匹配的
3. 如果上述两个条件都不满足则证明这个括号组合是有问题的，直接结束循环