(* 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.