首页 > 专题系列 > Java解POJ > POJ 1896 Code Formatting [解题报告] Java
2013
11-10

POJ 1896 Code Formatting [解题报告] Java

Code Formatting

问题描述 :

Programmers are known to wage religious wars when issues of proper code formatting are discussed. When new team of programmers starts working on a project, it often brings slightly different code formatting style and wants to reformat old source code according to their own style. Moreover, inexperienced programmers often neglect the importance of good and consistent code style, thus complicating the work of their teammates and themselves. This situation creates thriving market for code formatting tools.

You are taking part in a proof-of-concept project for a new code formatting tool code named Salvation. This is only a pilot project aimed not for a practical usefulness, but to demonstrate your ability to parse and format code of a high-level language. Your task is to write code formatter for a language called TRIVIAL (The Rival Implementation-Agnostic Language). This language has trivial lexical and grammatical structures. It does not have any keywords and control structures, because all constructs of the language are represented as function calls and closures.

The lexical structure consists of identifiers, opening and closing parenthesis and curly braces, commas, and semi-colons. Identifiers consist only of digits ’0′-’9′ and Latin letters ‘a’-'z’, ‘A’-'Z’. Lexical terms may be separated by whitespaces, leading and trailing whitespaces in the file are also allowed. Whitespace may consist of spaces, tab characters (ASCII code 9), and line separators (a pair of ASCII 13, 10).

The structure of the valid trivial program is derived from the following productions:

  • Program ::= Block
  • Block ::= ‘{‘ Statements ‘}’
  • Statements ::= Statement | Statement Statements
  • Statement ::= Expression ‘;’
  • Expression ::= identifier ['(' Arguments ')'] [Block]
  • Arguments ::= Expression | Expression ‘,’ Arguments

Properly formatted trivial program additionally conforms to the following rules:

  • There are no empty lines.
  • Tab characters are not used.
  • The first character of the file is opening curly brace ‘{‘ (no preceding whitespaces), and the last character of the file is closing curly brace ‘}’ (no trailing whitespaces).
  • Each line is preceded by 4N space characters, where N is called indentation level.
  • The first and the last lines of the program have zero indentation level.
  • Lines that constitute block body and are enclosed in curly braces ‘{‘. . . ‘}’ have one more indentation level.
  • No whitespace is allowed inside the line with the exception of the following two cases where a single space character is mandatory: before opening curly brace character ‘{‘ and after comma ‘,’.
  • Lines (with the only exception of the last line) end with semicolon ‘;’ or opening curly brace ‘{‘ characters. These characters cannot appear in the middle or at the beginning of any line (including the last one).
  • Closing curly brace ‘}’ characters appear only at the beginning of lines after indentation spaces.

See sample output section for an example of properly formatted trivial program.

输入:

The input contains valid trivial program. Size of each case does not exceed 2000 bytes.

输出:

Write to the output file properly formatted trivial code for the program given in the input file.

样例输入:

{class(Point) 
{
 member ( int ( x ) ) ; member ( int ( y ) ) ;
 member ( fun ( Length )  
 {
   return ( sqrt ( sum ( sqr ( x ),sqr ( y ) ) ) );
 } ) ;
};
Main 
{
 repeat 
 {
   set ( n,input ( int ) ) ;
   for ( int ( i,0 ) , lt ( i,n ) , inc ( i ) ) 
   {
     print ( mult ( n,n ) ) ;
   };
 };
}; }

样例输出:

{
    class(Point) {
        member(int(x));
        member(int(y));
        member(fun(Length) {
            return(sqrt(sum(sqr(x), sqr(y))));
        });
    };
    Main {
        repeat {
            set(n, input(int));
            for(int(i, 0), lt(i, n), inc(i)) {
                print(mult(n, n));
            };
        };
    };
}

解题代码:

//* @author:alpc12
import java.util.*;
import java.io.*;

public class Main {
 public static void main(String[] args) throws Exception {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  String line;
  StringBuffer sb = new StringBuffer();
  while ((line = in.readLine()) != null) {
	for (int i = 0; i < line.length(); i++) {
         char ch = line.charAt(i);
	  if (ch != ' ' && ch != 9)
		sb.append(ch);
	}
   }
  in.close();

  int indent = 1;
  boolean needws = true;
  System.out.println("{");
  for (int i = 1; i < sb.length(); i++) {
        char ch = sb.charAt(i);
	if (needws && ch != '}') {
		printws(indent);
		needws = false;
	}
      switch (ch) {
        case '{':
           System.out.println(" {");
           indent++;
           needws = true;
	    break;
	case '}':
	   needws = false;
	   indent--;
	   printws(indent);
	  System.out.print("}");
	  break;
      case ';':
	  System.out.println(";");
	  needws = true;
	  break;
      case ',':
	  System.out.print(", ");
	  break;
      default:
	  System.out.print(ch);
     }
  }
}

private static void printws(int indent) {
 for (int i = indent; --i >= 0;)
	System.out.print("    ");
 }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c