PROGRAM WFP$CANONICAL (OUTPUT);
    (* GENERATES WFP EXPRESSIONS IN SUCH A WAY THAT THE RIGHT
	(* SUBEXPRESSIONS CHANGE FIRST TO THEIR EXTREME CONFIGURATION
	(* WHILE LEFT SUBEXPRESION REMAINS THE SAME *****************)
	(* MODIFIED ON 3/8/86 TO GENERATE ALSO THE INFIX TRAVERSAL
	(* EXPRESSION OF EACH TREE GENERATED WITH CANONICAL POSTFIX
	(* TRAVERSAL EXPRESSION OF 1,2,3,4,5,...,N *******************)
	(*************************************************************)
	CONST	MAXLENG=20;
	TYPE	ARRRANGE = 1..MAXLENG;
	TYPE	STACKTYPE = ARRAY[ARRRANGE, 1..2] OF ARRRANGE;
		CHARST = PACKED ARRAY[ARRRANGE] OF CHAR;
	VAR	STACK:	STACKTYPE;
		TREESIZE,TOP,P,Q : ARRRANGE;
		I,J,COUNT: INTEGER;
		A:	CHARST;
	(*************************************************************)
	(*  PROCEDURES                                               *)
	(*************************************************************)
	PROCEDURE PRINTT;
	CONST	TWICEMAXLENG=40;
	VAR	M,N:INTEGER;
		TOP: ARRRANGE;
		INORDER$STACK : ARRAY[1..TWICEMAXLENG] OF 1..TWICEMAXLENG;
	BEGIN
	  COUNT := COUNT+1;
	  WRITE (COUNT:4, '*  ');
	  FOR M := 1 TO MAXLENG DO
             WRITE (A[M]);
	  (* CALCULATE INORDER SEQUENCE OF CURRENT TREE *********)
	     TOP := 0;
	     N   := 0;
	     FOR M := 1 TO 2*TREESIZE DO
	  	IF (A[M]='(') THEN
		  BEGIN
		  N := N+1;
		  TOP := TOP+1;
		  INORDER$STACK[TOP] := N;
		  END
		ELSE	(* A[M]=')', AND SO STACK NEEDS TO BE POPPED*)
		  BEGIN
		  WRITE (INORDER$STACK[TOP]:3);
		  TOP := TOP-1;
		  END;
	  WRITELN;
	END;	(* END-OF-PROCEDURE PRINTT ***************************)
	(*************************************************************)
	(*        PROCEDURE PUSH                                    **)
	(*************************************************************)
	PROCEDURE PUSH (VAR STACK:STACKTYPE;  VAR TOP:ARRRANGE;
                        POS,SIZE:ARRRANGE);
	BEGIN
	TOP := TOP+1;
	STACK[TOP,1] := POS;
	STACK[TOP,2] := SIZE;
	END;	(* END-OF-PROCEDURE PUSH *****************************)
	(*************************************************************)
	(*************************************************************)
	(*       PROCEDURE TREE$GENERATE                            **)
	(*************************************************************)
	PROCEDURE TREE$GENERATE (STACK:STACKTYPE; TOP:ARRRANGE);
	(* GLOBAL VARIABLES:
	(*  TREESIZE=SIZE OF THE ENTIRE TREE BEING CONSTRUCTED
	(*  COUNT   = COUNT OF EXPRESSIONS SO FAR GENERATED
	(*  A       = EXPRESSION CURRENTLY BEING GENERATED    ********)
	VAR	START,LENG,LAST,SAVETOP: ARRRANGE;
		LEFT,RIGHT,M,N,P: ARRRANGE;
	BEGIN
	  (* POP STACK TO GET INFORMATION ON CURRENT SUBTREE TO BE
	  (* GENERATED               *********************************)
	  START := STACK[TOP,1];
	  LENG  := STACK[TOP,2];
	  TOP := TOP-1;
	  SAVETOP := TOP;   (* SAVE CURRENT STACK-TOP *****************)
	  IF (LENG=1) THEN (* CURRENT TREE IS DONE **************************)
	    BEGIN
	    A[START] := '(';
	    A[START+1] := ')';
	    IF (TOP=0) THEN (* CURRENT GENERATION IS DONE *******************)
	      PRINTT
	    ELSE 
	      TREE$GENERATE(STACK,TOP);
	    END	  (* END-OF-LENG-BEING-ONE CASE *****************************)
	  ELSE    (* CURRENT TREE GENERATION IS NOT DONE ********************)
	          (**********************************************************)
	  FOR LEFT := LENG-1 DOWNTO 0 DO (*TO COVER LEFT SUBTREES OF DECREASING
	                             (* SIZES **************************)
	    BEGIN
	    TOP := SAVETOP;   (* RESTORE CURRENT STACK-TOP ***********)
	    RIGHT := LENG-LEFT-1;
	    IF (RIGHT>0) THEN (* RIGHT SUBTREE IS NONEMPTY *************)
               PUSH (STACK, TOP, START+(LENG-RIGHT)*2, RIGHT);
	    IF (LEFT>0)  THEN (* LEFT SUBTREE IS NONEMPTY ************)
	       PUSH (STACK, TOP, START+1, LEFT);
	    A[START] := '(';
	    A[START+2*LEFT+1] := ')';
	    TREE$GENERATE (STACK,TOP);
	    END;   (* END-OF-FOR LOOP TO COVER ALL DIFFERING SIZES OF
	         (* LEFT SUBTREES ************************************)
	END;     (* END-OF-PROCEDURE TREE$GENERATE *******************)
	(*************************************************************)
	(*             MAIN PROGRAM STARTS HERE                     **)
	(*************************************************************)
	BEGIN
	PAGE (OUTPUT);
	FOR TREESIZE := 1 TO 6 DO
	  BEGIN
	  WRITELN;
	  IF (TREESIZE > 4) THEN PAGE(OUTPUT);
	  WRITELN ('   LENGTH:', 2*TREESIZE:3);
	  WRITELN;
	  WRITELN ('     WFP EXPRESSIONS:    INORDER-TRAVERSAL');
	  WRITELN ('                         EXPRESSIONS' );
	  WRITELN;
	  COUNT := 0;
  	 (**** INITIALIZE OUTPUT STRING ARRAY AND STACK            **)
	  FOR I := 1 TO MAXLENG DO
	    A[I] := ' ';
	  TOP := 0;
	  PUSH (STACK, TOP, 1, TREESIZE);
	  TREE$GENERATE (STACK, TOP);
	  WRITELN;
	  END;
	PAGE (OUTPUT);
	END.