NYOJ题目2——括号配对问题

Sep 18, 2017 阅读(195)

标签: 算法 NYOJ

来源:http://acm.nyist.net/JudgeOnline/problem.php?pid=2

  • 描述

  • 现在,有一行括号序列,请你检查这行括号是否配对。


  • 输入

    第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符


    输出

    每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No


    样例输入

    3
    [(])
    (])
    ([[]()])

    样例输出

    No
    No
    Yes


思路:

括号配对,解题出路是将配对的数据进行消除,全部消除完毕则配对成功,否则配对失败。有些类似曾经玩的游戏俄罗斯方块游戏的匹配消失。

在下面代码中使用了两种消除模式,一种通过ASCII码的差值来比较配对,一种是硬编码比较方式来配对消除。


C/C++:

#include<stdio.h>
#define N 10000+10
char s[N];

int main()
{
	int n;
	char c,*p;
	scanf("%d\n",&n);
	while(n--){
		*s=getchar();
		p=s+1;
		while((c=getchar())!='\n'){
			if(*(p-1)==c-1||*(p-1)==c-2)
				p--;
			else
				*p++=c;
		}
		if(p==s)
			printf("Yes\n");
		else
			printf("No\n");
	}
}

JAVA:

import java.util.Scanner;
public class Main {
	static char[] stack = new char[10000];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		while (n-- > 0) {
			if(check(scan.next().trim())){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}
		scan.close();
	}
	
	private static boolean check(String line){
		if(line.length() % 2 == 1) return false;
		
		int point = 0;
		char[] charArray = line.toCharArray();
		for (int i = 0; i < charArray.length; i++) {
			char c = charArray[i];
			if(')' == c ){
				if( '(' == stack[point]){
					point--;
				}else{
					return false;
				}
			}else if(']' == c){
				if( '[' == stack[point]){
					point--;
				}else{
					return false;
				}
			}else{
				stack[++point] = c;
			}
		}
		
		return ( 0 == point) ? true : false;
	}
}