首页 > 专题系列 > Java解POJ > POJ 1126 Simply Syntax [解题报告] Java
2013
11-09

POJ 1126 Simply Syntax [解题报告] Java

Simply Syntax

问题描述 :

In the land of Hedonia the official language is Hedonian. A Hedonian professor had noticed that many of her students still did not master the syntax of Hedonian well. Tired of correcting the many syntactical mistakes, she decided to challenge the students and asked them to write a program that could check the syntactical correctness of any sentence they wrote. Similar to the nature of Hedonians, the syntax of Hedonian is also pleasantly simple. Here are the rules:

0.The only characters in the language are the characters p through z and N, C, D, E, and I.

1.Every character from p through z is a correct sentence.

2.If s is a correct sentence, then so is Ns.

3.If s and t are correct sentences, then so are Cst, Dst, Est and Ist.

4.Rules 0. to 3. are the only rules to determine the syntactical correctness of a sentence.

You are asked to write a program that checks if sentences satisfy the syntax rules given in Rule 0. – Rule 4.

输入:

The input consists of a number of sentences consisting only of characters p through z and N, C, D, E, and I. Each sentence is ended by a new-line character. The collection of sentences is terminated by the end-of-file character. If necessary, you may assume that each sentence has at most 256 characters and at least 1 character.

输出:

The output consists of the answers YES for each well-formed sentence and NO for each not-well-formed sentence. The answers are given in the same order as the sentences. Each answer is followed by a new-line character, and the list of answers is followed by an end-of-file character.

样例输入:

Cp
Isz
NIsz
Cqpq

样例输出:

NO
YES
YES
NO

解题代码:

方法一:
import java.util.Scanner;

public class Main {

/**
* @param args
*/

public static void main(String[] args) {
 Scanner s = new Scanner(System.in);
 String sentence = null;
 int count;
 char ch;
 while ((sentence = s.nextLine()) != null) {
   count = 0;// 当前句子数
   for (int i = sentence.length() - 1; i >= 0; i--) {
    ch = sentence.charAt(i);
    if (ch >= 'p' && ch <= 'z') {
      count++;
    } else if (ch == 'C' || ch == 'D' || ch == 'E' || ch == 'I') {
      count--;
   if (count < 1)
     break;
   } else if (ch == 'N') {
     if (count < 1)
       break;
     } else {
       count = -1;
       break;
     }
   }
   if (count == 1) {
     System.out.println("YES");
   } else {
     System.out.println("NO");
   }
  }
 }
}


方法二:
import java.util.Scanner;

public class Main {//递归实现
 public static void main(String[] args) {
  Scanner s = new Scanner(System.in);
  String sentence = null;
  while ((sentence = s.nextLine()) != null) {
	if (isSentence(sentence, 0, sentence.length() - 1)) {
	  System.out.println("YES");
	} else {
	  System.out.println("NO");
	}
   }
  }

 private static boolean isSentence(String sentence, int start, int end) {
  char ch = sentence.charAt(start);
  if (start == end) {
	if (ch >= 'p' && ch <= 'z') {
          return true;
	} else {
	  return false;
	}
  } else if (ch == 'N' && isSentence(sentence, start + 1, end)) {
	return true;
  } else if (ch == 'C' || ch == 'D' || ch == 'E' || ch == 'I') {
	for (int i = 1; i < end - start; i++) {
	  if (isSentence(sentence, start + 1, start + i)
	    && isSentence(sentence, start + i + 1, end)) {
		return true;
	    }
	}
	return false;
   }
   return false;
  }
}