COCS3308                  Program-2         	Due: 9/27/2006
	       Well-formed parenthesis (WFP) expression Generation
						
     THE FOLLOWING CFG MAY DEFINE THE SET OF WELL-FORMED PARENTHESIS (WFP) EXPRESSIONS:
  
		S -> S R 
		S -> R
		R -> ( S ) 
		R -> ( )  

     Objectives:

     1. Appreciate the practical utility of unambiguous grammars.
     2. Understand the process of leftmost derivations in obtaining all possible derivations. 	
  
     Task:
     Your task is to write a well-structured program (in any language of your choice) 
     that generates and prints all different expressions for length of 8, 10, 12, and 14 respectively.
     For example, for the length of 4,
	we have two such expressions:	
			(())
			()()
	and for the length of 6,
	we have five such expressions:	
			((()))
			(()())
			(())()
			()(())
			()()()

     SUGGESTED Functions
  
     1.  void S(int N, int POS, CHARSTRING A)
           { 
	     // N is the number of nonterminals yet to be derived and
	     // it is initially half the length being sought.
	     CHARSTRING Save;
	     if (N==0) PRINT(A,POS)  
			// TO PRINT AN EXPRESSION found 
          		// AFTER CONVERTING EVERY NONTERMINAL TO "()"
 	     else  
		  {
		  strcpy(Save,A);
		  RULE1 (N,POS,A);  // TO APPLY RULE#1 AND THEN 
                                    // RECURSIVELY CALL S() to continue
		  strcpy(A,Save);
		  RULE2 (N,POS,A);  // TO APPLY RULE#2 AND THEN
                                    // call R() to continue
		  }
           }
	   // End of S()
 
     2.  void R(SAME PARAMETERS)
	   { 
	     Charstring Save;
  	     if (N==0) PRINT(A,POS);
  	     else  
	     { 
	       strcpy(Save,A);
	       RULE3 (N,POS,A);    // TO APPLY RULE#3 AND THEN CALL S() to
				   // continue
	       strcpy(A,Save);
	       RULE4 (N,POS,A);    // TO APPLY RULE#4, LOCATE NEXT
                                   // NONTERMINAL R AND CALL R() to continue
	     }
           }  // END of R()
 
     3. void RULE1 (int MORENONT, int POS, CHARSTRING A)
        { // Applying the rule-1: S -> S R
          int M;
          for ( M=MAXSIZE-1; M>=POS+1; M--)
            A[M+1]=A[M];
          A[POS+1] := 'R';
          S(MORENONT-1,POS,A); 	
		// as the result of applying rule-1, the number of remaining 
		// nonterminals is reduced by one.
        } // end of RULE1()
  
     4. OTHER functions:
        	RULE2
		RULE3
		RULE4
		PRINT(A, Pos) 
		// This function will print the string
		// contents of 'A' after converting each remaining
		// nonterminal to be found beyond the given position
		// into "()"