栈实现括号匹配

客官°小女子只卖身不卖艺 2022-04-12 14:14 163阅读 0赞

现在有圆括号 ()、方括号 \[\] 和花括号 \{\}，将它们任意嵌套 `{[(3+2) * 2] + 3}` 是合法的格式， `{[(3+2 * 2] + 3}` 是不合法的格式。

现在用栈来解决这个问题，栈是一种后进先出的数据结构。将扫描到的左括号压入栈中，遇到右括号则中栈中取出一个左括号看是否匹配，如果不匹配或栈为空（说明栈中没有左括号了）格式就不合法。当所有字符都扫描完之后，如果栈不为空，说明还有无法配对的左括号，此时格式也是不合法的。

参考 Java 的 Stack 实现一个简单栈：

public class MyStack<E> { 
        /** * 栈中的元素个数 */
        private int count;
        private Object[] elements;
    
        public MyStack() { 
            this(10);
        }
    
        public MyStack(int initialCapacity) { 
            this.elements = new Object[initialCapacity];
        }
    
        public E push(E item) { 
            // 判断这个栈是否需要扩容
            ensureCapacity(count + 1);
            elements[count++] = item;
            return item;
        }
    
        @SuppressWarnings("unchecked")
        public E pop() { 
            // 栈为空
            if (this.isEmpty()) { 
                return null;
            }
            E obj = (E) elements[count - 1];
            count--;
            elements[count] = null;
            return obj;
        }
    
        public boolean isEmpty() { 
            return count == 0;
        }
    
        private void ensureCapacity(int minCapacity) { 
            if (minCapacity - elements.length > 0) { 
                // 扩容为原先数组的 2 倍
                int newCapacity = 2 * elements.length;
                elements = Arrays.copyOf(elements, newCapacity);
            }
        }
    }

通过栈实现括号匹配

public class StackDemo { 
        public static void main(String[] args) { 
            String a = "{[(3+2) * 2] + 3}[][";
            String b = "{[(3+2) * 2] + 3}[][]";
            String c = "{[(3+2) * 2] + 3}[][]]]]";
            boolean resA = isParenthesisMatch(a);
            boolean resB = isParenthesisMatch(b);
            boolean resC = isParenthesisMatch(c);
            // false
            System.out.println(resA);
            // true
            System.out.println(resB);
            // false
            System.out.println(resC);
    
        }
    
        public static boolean isParenthesisMatch(String str) { 
            MyStack<Character> stack = new MyStack<>();
            for (Character ch : str.toCharArray()) { 
                switch (ch) { 
                    case '(':
                    case '[':
                    case '{':
                        stack.push(ch);
                        break;
                    case ')':
                        if (stack.isEmpty()) { 
                            return false;
                        }
                        if (!stack.pop().equals('(')) { 
                            return false;
                        }
                        break;
                    case ']':
                        if (stack.isEmpty()) { 
                            return false;
                        }
                        if (!stack.pop().equals('[')) { 
                            return false;
                        }
                        break;
                    case '}':
                        if (stack.isEmpty()) { 
                            return false;
                        }
                        if (!stack.pop().equals('{')) { 
                            return false;
                        }
                        break;
                    default:
                        System.out.println(ch + ": mapping none");
                        break;
    
                }
            }
            if (!stack.isEmpty()) { 
                return false;
            }
            return true;
        }
    }