【数据结构】Java实现括号匹配问题

比眉伴天荒 2023-06-11 08:29 1阅读 0赞

### 问题描述 ###

**编写一个类，从标准输入中读取一串包含"(" “)” “\[” “\]” “\{” "\}"的字符串，并使用栈来判定其中的括号是否配对完整。例如 “\[()\]\{\}\{\[()()\] ()\}”程序应该打印true，对于 \[(\]) 则打印false.**

### 算法 ###

1.将字符串转换为字符数组chars  
2.利用for循环，将每一次读取到的字符chars\[i\]与(,\[,\{进行比较，若匹配，则将chars\[i\]压入栈中；否则，进入3.  
3.将chars\[i\]与），\]，\}进行比较。这里以）为例进行说明，若chars\[i\]=’)’，则与栈顶元素top进行比较，若栈顶元素为’(’，则匹配，将栈顶元素pop出；若栈顶元素不为‘（’，则不匹配，返回false，退出循环  
4.当所有chars\[i\]都遍历完成，退出循环，返回true，证明括号全部匹配

### 代码实现 ###

1.链表实现栈  
ListStack.java

package cn.Day06_栈.demo2;
    
    /** * 链表实现栈 */
    public class ListStack<Item> { 
        private class Node{ 
            //结点的嵌套类型
            Item item;
            Node next;
        }
        private Node first;//栈顶（最新添加的元素）
        private int num;//栈中元素的数目
    
        /** * 判断栈是否为空 * @return 空：true 非空：false */
        public boolean isEmpty(){ 
            if (first==null){ 
                return true;
            }
            return false;
        }
    
        /** * 返回栈中元素的个数 * @return */
        public int size(){ 
            return num;
        }
    
        /** * 入栈 */
        public void push(Item item){ 
            Node oldfirst=first;
            first=new Node();
            first.item=item;
            first.next=oldfirst;//新的元素指向旧的元素
            num++;
        }
    
        /** * 出栈 * @return 返回出栈元素的包含内容 */
        public Item pop(){ 
            Item item=first.item;
            first=first.next;//设置新栈顶元素为原栈顶元素的前一个结点
            num--;
            return item;
        }
        /** * 输出栈顶元素，但不pop出 */
        public Item getTop(){ 
            return first.item;
        }
    
        /** * 输出栈 */
        public void PrintfStack(){ 
            Node temp=first;
            if (first==null){ 
                System.out.println("栈为空，无法输出");
            }
            while (temp!=null){ 
                System.out.printf(temp.item+" ");
                temp=temp.next;
            }
    
        }
    
    }

2.括号匹配类  
MatchBrackets.java

package cn.Day06_栈.demo2;
    
    import java.util.Scanner;
    
    public class MatchBrackets { 
        public static boolean isMatch(String expression){ 
            if (expression==null){ 
                return false;
            }
            ListStack<Character> stack = new ListStack<>();//字符类类型
            char[] chars=expression.toCharArray();//将字符串转为字符数组
            for (int i = 0; i < chars.length; i++) { 
                if ((chars[i]=='(')||(chars[i]=='[')||(chars[i])=='{'){ 
                    stack.push(chars[i]);
                }else if (chars[i]==')'){ 
                    if (!stack.isEmpty()){ 
                        Character top = stack.getTop();
                        if (top=='('){ 
                            stack.pop();
                            continue;
                        }else { 
                            return false;//不匹配
                        }
                    }else{ 
                        return false;//不匹配
                    }
                }else if (chars[i]=='}'){ 
                    if (!stack.isEmpty()){ 
                        Character top = stack.getTop();
                        if (top=='{'){ 
                            stack.pop();
                            continue;
                        }else { 
                            return false;//不匹配
                        }
                    }else{ 
                        return false;//不匹配
                    }
    
                }else { 
                    if (!stack.isEmpty()){ 
                        Character top = stack.getTop();
                        if (top=='['){ 
                            stack.pop();
                            continue;
                        }else { 
                            return false;//不匹配
                        }
                    }else { 
                        return false;//不匹配
                    }
                }
            }
            return true;
        }
    
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            while (true){ 
                System.out.println("请输入一串括号：");
                String expression = scanner.next();
                System.out.println("这串括号是否匹配："+MatchBrackets.isMatch(expression));
                System.out.println("请问是否继续输入（y表示是/n表示否）：");
                String flag = scanner.next();
                if (flag.equals("y")){ 
                    continue;
                }
                if (flag.equals("n")){ 
                    break;
                }
            }
            System.out.println("测试结束！");
        }
    }

3.测试

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]2019.10.29日算法与数据结构打卡~  
有不懂的朋友可以私信我一起交流！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230531/11e5fd2760de49358b31e9bd6bf498de.png