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.