{ Evaluate numeric expressions prersented in the form of a parse tree }

program evaluate(input, output);

{  There are two sorts of expression nodes in the tree; those which simply
   contain a number and those which contain an operator whose operands require
   further evaluation.
   If eexptype = number, this node holds a literal integer in the value field
   and the eoperator and eleft- and eright- operand fields are not used.
   Otherwise the evalue field is not used, and the two operand fields point
   to the expressions which evaluate to the left and right operands of the
   operator in eoperator
}

type
   exptype  = ( number, subexpression );
   operator = ( plus, minus, times );

   eptr = ^expression;
   expression =
      record
         eexptype      : exptype;     { What sort of expression this node is }
         evalue        : integer;     { The result if eexptype = number      }
	 eoperator     : operator;    { otherwise apply this operator        }
         eleftoperand  : eptr;        { using pointer to left operand        }
         erightoperand : eptr;        { and pointer to right operand         }
      end;
   
{ Return a pointer to the top node of the parse tree for an arithmetic
  expression }

function expr : eptr;
   var
      node1, node2, node3, node4, node5, node6, node7, node8, node9 : eptr;
      node10, node11, node12, node13 : eptr;
   begin
      { You are not supposed to understand this but you are welcome to try! }
      new(node1); new(node2); new(node3); new(node4); new(node5);
      new(node6); new(node7); new(node8); new(node9); new(node10);
      new(node11); new(node12); new(node13);
      node1^.eexptype := number; node2^.eexptype := number;
      node3^.eexptype := number; node4^.eexptype := number;
      node5^.eexptype := number; node6^.eexptype := number;
      node7^.eexptype := number; node8^.eexptype := subexpression;
      node9^.eexptype := subexpression; node10^.eexptype := subexpression;
      node11^.eexptype := subexpression; node12^.eexptype := subexpression;
      node13^.eexptype := subexpression;
      node1^.evalue := 0; node2^.evalue := 6; node3^.evalue := 6;
      node4^.evalue := 6; node5^.evalue := 4; node6^.evalue := 3;
      node7^.evalue := -1;
      node8^.eoperator := minus; node9^.eoperator := times;
      node10^.eoperator := times; node11^.eoperator := times;
      node12^.eoperator := minus; node13^.eoperator := plus;
      node8^.eleftoperand := node1; node9^.eleftoperand := node3;
      node10^.eleftoperand := node5; node11^.eleftoperand := node6;
      node12^.eleftoperand := node9; node13^.eleftoperand := node8;
      node8^.erightoperand := node2; node9^.erightoperand := node4;
      node10^.erightoperand := node11; node11^.erightoperand := node7;
      node12^.erightoperand := node10; node13^.erightoperand := node12;
      expr := node13;
   end;

{ Evaluate the parse tree to a final value }
function evaluate(expr:eptr):integer;
   begin
      with expr^ do
	 case eexptype of
	 number:
	    evaluate := evalue;
	 subexpression:
	    case eoperator of
	    plus:
	       evaluate := evaluate(eleftoperand)
			 + evaluate(erightoperand);
	    minus:
	       evaluate := evaluate(eleftoperand)
			 - evaluate(erightoperand);
	    times:
	       evaluate := evaluate(eleftoperand)
			 * evaluate(erightoperand);
	    end;
	 end;
   end;

begin
   writeln ( evaluate ( expr ) );
end.