Code Formatting

Time limit2sMemory limit128 MB

Summary

Parse a TRIVIAL program given by a grammar and print it back with strict indentation and whitespace rules.

Level: Medium6 of 10
Topics: Implementation, Recursion, String, Simulation
Solved: No attempts yet

Problem

Programmers often disagree about proper code formatting. When a new team starts on a project, they frequently want to reformat existing source code to match their own style, and inconsistent formatting makes everyone's work harder. This has created a healthy market for code formatting tools.

You are working on a proof-of-concept for a new formatting tool codenamed Salvation. The goal is not practical usefulness but to demonstrate that you can parse and format the code of a high-level language. Your task is to write a formatter for a language called TRIVIAL (The Rival Implementation-Agnostic Language). This language has a trivial lexical and grammatical structure: it has no keywords and no control structures, because every construct is expressed as a function call or a closure.

The lexical structure consists of identifiers, opening and closing parentheses and curly braces, commas, and semicolons. Identifiers consist only of the digits 0-9 and the Latin letters a-z, A-Z. Lexical tokens may be separated by whitespace, and leading and trailing whitespace is allowed. Whitespace may consist of spaces, tab characters (ASCII code 9), and line separators (a pair of ASCII 13, 10).

A 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

A properly formatted TRIVIAL program additionally satisfies the following rules:

There are no empty lines.
Tab characters are not used.
The first character of the file is an opening curly brace { with no preceding whitespace, and the last character is a closing curly brace } with no trailing whitespace.
Each line is preceded by $4N$ space characters, where $N$ is called the indentation level.
The first and last lines of the program have indentation level zero.
Lines that form a block body enclosed in curly braces {...} have an indentation level one greater than the enclosing line.
No whitespace is allowed inside a line, with exactly two exceptions where a single space character is mandatory: before an opening curly brace {, and after a comma ,.
Every line except the last ends with a semicolon ; or an opening curly brace {. These two characters may never appear in the middle of a line or at the beginning of any line (including the last one).
Closing curly braces } appear only at the beginning of a line, right after the indentation spaces.

See the example cases for what a properly formatted TRIVIAL program looks like.

Input

The input contains one valid TRIVIAL program. Its size does not exceed 2000 bytes.

Output

Print the properly formatted TRIVIAL code for the program given in the input.

Examples3

Example 1

Input

{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 ) ) ;
   };
 };
}; }

Expected output

{
    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));
            };
        };
    };
}

Example 2
Input
```
{a;}
```
Expected output
```
{
    a;
}
```

Example 3

Input

{  foo ( a , b , c ) ; }

Expected output

{
    foo(a, b, c);
}