问题描述
编写一个类，从标准输入中读取一串包含"(" “)” “[” “]” “{” "}"的字符串，并使用栈来判定其中的括号是否配对完整。例如 “[()]{}{[()()] ()}”程序应该打印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.测试
有不懂的朋友可以私信我一起交流！
