(* Note that Due to html sybtax conflict, "<" is replaced by "%"
	(*   FILE: WFP.html
	(* THIS PROGRAM GENERATES AND PRINTS WELL-FORMED PARENTHESIS
	(* EXPRESSIONS FOR GIVEN LENGTH.
	(* ROUTINES CALLED INCLUDE:
	(* 1. RULE1: TO APPLY RULE:  W ---> W R
	(* 2. RULE2: TO APPLY RULE:  W ---> R 
	(* 3. RULE3: TO APPLY RULE:  R ---> ( W ) 
	(* 4. RULE4: TO APPLY RULE:  R ---> ( ) 
	(* 5. PRINT$
	(* 6. W$
	(* 7. R$
	(***********************************************************)
	PROGRAM WFPCOUNT (INPUT,OUTPUT);
	CONST 	MAXLEN=40;
	TYPE	CHARSTRING=PACKED ARRAY [1..MAXLEN] OF
			CHAR;
	VAR	MAXSIZE, COUNT$EXP, M, N, P: INTEGER;
		A : CHARSTRING;
	Var OutFile: TEXT;
	(************************************************************)
	(*                                                          *)
	(* NESTED ROUTINES FOLLOW HERE                              *)
	(*                                                          *)
	(************************************************************)
	  PROCEDURE W$ (N,POS : INTEGER; A : CHARSTRING); FORWARD;
	  PROCEDURE R$ (N,POS : INTEGER; A : CHARSTRING); FORWARD;
	(************************************************************)
	(*   PROCEDURE RULE1 (MORENONT, POS: INTEGER; A: CHARSTRING)*)
	(************************************************************)
	  PROCEDURE RULE1 (MORENONT,POS:INTEGER; A:CHARSTRING);
	  VAR	M,N: INTEGER;
	  BEGIN
	 	FOR M := MAXSIZE*2-2*MORENONT-1 DOWNTO POS+1 DO
		   A[M+1] := A[M];
		A[POS+1] := 'R';
		W$ (MORENONT, POS, A);
	  END;  (* END OF PROCEDURE RULE1 **************************)
	(***********************************************************)
	(* PROCEDURE RULE2                                        **)
	(*                                                        **)
	PROCEDURE RULE2 (MORENONT,POS: INTEGER; A:CHARSTRING);
	BEGIN
		A[POS] := 'R';
		R$ (MORENONT, POS, A);
	END;	(* END OF PROCEDURE RULE2 **************************)
	(***********************************************************)
	(*	PROCEDURE RULE3 ************************************)
	(*                      ************************************)
	(***********************************************************)
	PROCEDURE RULE3 (MORENONT,POS: INTEGER; A:CHARSTRING);
	VAR M,N:INTEGER;
	BEGIN
		FOR M:= MAXSIZE*2-2*MORENONT-2 DOWNTO POS+1 DO
			A[M+2] := A[M];
		A[POS] := '(';
		A[POS+1] := 'W';
		A[POS+2] := ')';
		W$ (MORENONT, POS+1, A);
	END;	(* END OF PROCEDURE RULE3 *************************)
	(**********************************************************)
	(*	PROCEDURE RULE4           *************************)
	(*                                *************************)
	(**********************************************************)
	PROCEDURE RULE4 (MORENONT,POS:INTEGER; A:CHARSTRING);
	VAR	M,NEXTPOS: INTEGER;
	BEGIN
		NEXTPOS := 0;
		FOR M:= MAXSIZE*2- 2*MORENONT - 1 DOWNTO POS+1 DO
		  BEGIN
		  A[M+1] := A[M];
		  IF (A[M+1] = 'R') THEN NEXTPOS:=M+1;
		  END;	(* END OF FOR-LOOP ***********************)
		A[POS] := '(';
		A[POS+1] := ')';
		IF NEXTPOS %> 0 THEN 
		  R$ (MORENONT, NEXTPOS, A);
	END;	(* END OF PROCEDURE RULE4 ************************)
	(*********************************************************)
	(*	PROCEDURE PRINT$                     *************)
	(*********************************************************)
	PROCEDURE PRINT$ ( A: CHARSTRING; POS: INTEGER );
	VAR	M,N : INTEGER;
		(* COUNT$EXP=GLOBAL VARIABLE COUNTING ALL EXPRESSIONS
		(*           SO FAR GENERATED **********************)
	BEGIN
		COUNT$EXP := COUNT$EXP+1;
		FOR M := POS TO MAXSIZE*2 DO
		  BEGIN
		  IF (A[M]='W') OR (A[M]='R') THEN
		    BEGIN
		    FOR N := MAXSIZE*2 DOWNTO M+1 DO
			A[N] := A[N-1];
		    A[M]    := '(';
		    A[M+1]  := ')';
		    END;	(* END OF W-OR-R CASE *************)
		  END;	(* END OF FOR-LOOP ************************)
		WRITELN (OutFile, COUNT$EXP:3, ':::', A);
	END;	(* END OF PROCEDURE PRINT$ ************************)
	(**********************************************************)
	(*	PROCEDURE W$                           ************)
	(**********************************************************)
	PROCEDURE W$  (**  (N,POS: INTEGER; A:CHARSTRING)  **) ;
	BEGIN
	  IF (N=0) THEN PRINT$(A,POS)
	  ELSE
		BEGIN
		RULE1(N-1,POS,A);
		RULE2(N,POS,A);
		END;
	  END;	(* END OF PROCEDURE-W ****************************)
	(*********************************************************)
	(*    PROCEDURE R$; FORWARD                   ************)
	(*********************************************************)
	PROCEDURE R$ (* N,POS:INTEGER; A:CHARSTRING ************) ;
	BEGIN
	  IF (N=0) THEN PRINT$(A,POS)
	  ELSE
		BEGIN
		RULE3(N-1, POS, A);
		IF (A[POS+1] %> ' ') THEN (* CURRENT NONTERMINAL
                    (* IS NOT THE LAST ONE GENERATED ******)
		  RULE4 (N, POS, A);
		END;
	END;	(* END OF PROCEDURE-R ***************************)
	(*********************************************************)
	(**       MAIN PROGRAM STARTS HERE ***********************)
	(*********************************************************)
	BEGIN
		Open (OutFile, 'Wfp.out', New);
		ReWrite (OutFile);
		FOR MAXSIZE := 2 TO 6 DO
		  BEGIN
		  COUNT$EXP := 0;
		  WriteLn (OutFile);
		  WRITELN(OutFile, 'LENGTH:', MAXSIZE:4);
		  WRITELN(OutFile);
		  FOR M := 1 TO MAXLEN  DO
			A[M] := ' ';
		  A[1]:='W';	(*WITHOUT THIS INITIALIZATION, FIRST
		                (*EXPRESSION BECOMES SHORTER ******)
		  W$ (MAXSIZE-1, 1, A);
		  WRITELN(OutFile);
		  WRITELN (OutFile, ' TOTAL COUNT:', COUNT$EXP:4);
		  WriteLn (OutFile);
		  END; (* END OF FOR-LOOP *******************)
	END.