括号配对问题
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 现在,有一行括号序列,请你检查这行括号是否配对。
- 输入
- 第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
- 输出
- 每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No
- 样例输入
-
3 [(]) (]) ([[]()])
- 样例输出
-
No No Yes
//不用栈的情况,用数组超时
import java.util.Scanner; public class Main {//NYOJ02---括号配对问题 public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); while(n-->0){ String str=input.next(); boolean ok=true; int e=0; Is is[]=new Is[10000];//相当于栈 for(int i=0;i<str.length();i++){ if(str.charAt(i)=='['||str.charAt(i)=='('){ is[e++]=new Is(str.charAt(i));//如果是左括号,进栈 continue; } if(e==0){//是右括号且栈空,不配对 System.out.println("No"); ok=false;//标志一下防止多次输出No break; } if(str.charAt(i)==')'&&is[e-1].a=='(')//栈不为空且配对,出栈 e--; else if(str.charAt(i)==']'&&is[e-1].a=='[') e--; else{//不配对 System.out.println("No"); ok=false; break; } } if(ok&&e==0){//最后栈为空,配对 System.out.println("Yes"); } else if(ok)//防止多次输出No System.out.println("No"); } } } class Is{//相当于栈 char a='0'; Is(char a){ this.a=a; } }
用栈:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { // Scanner in = new Scanner(System.in); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = null; Stack<Character> stack = new Stack<Character>(); // int cases = in.nextInt(); try{ int cases = Integer.valueOf(br.readLine()); while(cases-->0){ // str = in.next(); str = br.readLine(); int strLength = str.length(); boolean isMatch = true; stack.clear(); stack.push('#'); for(int i = 0; i < strLength; ++i){ char ch = str.charAt(i); switch(ch){ case '(': stack.push(ch); break; case '[': stack.push(ch); break; case ')': if(stack.pop() != '('){ isMatch = false; } break; case ']': if(stack.pop() != '['){ isMatch = false; } break; default: isMatch = false; break; } if(!isMatch){ break; } } if(isMatch&&stack.pop()=='#'){ System.out.println("Yes"); }else{ System.out.println("No"); } } }catch(Exception e){ e.printStackTrace(); } } }