括号匹配问题的记录

假设表达式中包含三种括号：圆括号、方括号和花括号，它们可以互相嵌套，如{[()]}，{[]}等均为正确的格式，而不对称的均为不正确的格式。

解:

public class BracketMatch {

    /**
     * 算法思路：
     *   1、因为括号都是左右对称的，那么，我们可以遇到左括号就把把它收起来，
     *   2、遇到右括号就拿最后一个放入的左括号进行匹配
     *   如果相匹配，继续进行1
     *   如果不匹配，则退出匹配并给出提示。
     *
     *   每次都拿最后一个，这里用栈比较合适，所有我们定义一个栈来存左括号
     */
    public static void main(String[] args) {
        String str = "([[](){}{()[()]}]";
        char[] chars = str.toCharArray();
        StackQueue queue = new StackQueue();
        for (int i = 0; i < chars.length; i++) {
            switch (chars[i]){
                case '(':
                case '[':
                case '{':
                    queue.push(chars[i]);
                    break;
                case ')':
                case ']':
                case '}':
                    if (queue.isEmpty()){
                        System.out.println("右括号多余！");
                        return;
                    }else {
                        char c = queue.getTop();
                        if (match(c,chars[i])){
                            queue.pop();
                        }else {
                            System.out.println("对应的左右括号不同类！");
                            return;
                        }
                    }
            }
        }
        if (queue.isEmpty()){
            System.out.println("括号匹配！");
        }else {
            System.out.println("左括号多余！");
        }
    }

    /**
     * 对比左右括号是否相匹配
     * @param left
     * @param right
     * @return
     */
    public static boolean match(char left, char right) {
        boolean result = false;
        switch (left){
            case '(':
                result = right == ')';
                break;
            case '[':
                result = right == ']';
            break;
            case '{':
                result = right == '}';
            break;
        }
        return result;
    }

    /**
     * 定义结点（栈）
     */
    static class StackNode {
        public char c ;
        public StackNode next = null;

        public StackNode(char c, StackNode next) {
            this.c = c;
            this.next = next;
        }
    }

    /**
     * 定义栈
     */
    static class StackQueue {
        StackNode top = null;
        int length = 0;

        //入栈操作
        public void push(char c){
            if (top == null){
                top = new StackNode(c,null);
            }
            StackNode node = new StackNode(c,null);
            node.next = top;
            top = node;
            length++;
        }

        //出栈操作
        public char pop(){
            if (length <= 0){
                new Exception("空栈，无元素！");
                return ' ';
            }
            char c = top.c;
            top = top.next;
            length--;
            return c;
        }

        //得到栈顶元素
        public char getTop(){
            if (length <= 0){
                new Exception("空栈，无元素！");
                return ' ';
            }
            return top.c;
        }

        //判断栈是否为空
        public boolean isEmpty(){
            return length == 0;
        }
    }
}