{ Read numeric expressions from the input, evaluate them and print the result
  on the output. An expression is defined as:			

  expression ::= <integer>
	      or <expression> <operator> <expression>

  operator   ::= '+'
	      or '-'
	      or '*'
}

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;
   
var
   debug : boolean;		{ debugging trace }

{
   read one line from the input, parse it and return a pointer to the root of
   the parse tree.
}

function readexpression:eptr;

   {
      this function requires two stacks to do its work, which are implemented by
      linked lists. Sub-functions:

      priority:  return priority of an operator; the higher, the more binding
      ReadRator: return next operator from input stream
      ReadRand:  return next operand from input stream
      InitStacks: initialise the operator and operand stacks
      TopRator:  return operator on top of operator stack (do not pop)
      PushRator: push an operator onto the operator stack
      PopRator:  pull an operator from the top of the operator stack
      PushRator, PushRand: Ditto for operand stack
   }

   type
      { type of cells on operator stack }
      RatorPtr = ^RatorCell;
      RatorCell =
	 record
	    rator : operator;
	    next : RatorPtr;
	 end;
      
      { type of cells on operand stack }
      RandPtr = ^RandCell;
      RandCell =
	 record
	    rand : eptr;
	    next : RandPtr;
         end;
      
   var
      RatorHead : RatorPtr;
      RandHead  : RandPtr;
      
   { Stack handling functions }

   { initialise the stacks }
   procedure initstacks;
      begin
	 RatorHead := nil;
	 RandHead  := nil;
      end;

   { is the operand stack empty? }
   function EmptyRand:boolean;
      begin
	 EmptyRand := ( RandHead = nil );
      end;

   { is the operator stack empty? }
   function EmptyRator:boolean;
      begin
	 EmptyRator := ( RatorHead = nil );
      end;

   procedure PushRand(rand : eptr);
      var
	 newcell : RandPtr;
      begin
	 new(newcell);
	 newcell^.rand := rand;
	 newcell^.next := RandHead;
	 RandHead      := newcell;
      end;

   procedure PushRator(rator : operator);
      var
	 newcell : RatorPtr;
      begin
	 new(newcell);
	 newcell^.rator := rator;
	 newcell^.next  := RatorHead;
	 RatorHead      := newcell;
      end;

   function PopRand:eptr;
      var
	 { used to remember the old cell to free it when we have sucked it dry}
	 oldcell : RandPtr;
      begin
	 if EmptyRand
	 then
	    begin
	       writeln('Panic: PopRand called with empty stack');
	       halt;
	    end;
	 PopRand := RandHead^.rand;
	 oldcell := RandHead;
	 RandHead := RandHead^.next;
	 dispose(oldcell);
      end;

   function PopRator:operator;
      var
	 { used to remember the old cell to free it when we have sucked it dry}
	 oldcell : RatorPtr;
      begin
	 if EmptyRator
	 then
	    begin
	       writeln('Panic: PopRator called with empty stack');
	       halt;
	    end;
	 PopRator := RatorHead^.rator;
	 oldcell := RatorHead;
	 RatorHead := RatorHead^.next;
	 dispose(oldcell);
      end;

   { peek at the top operator on the stack }
   function TopRator:operator;
      begin
	 if EmptyRator
	 then
	    begin
	       writeln('Panic: TopRator called with empty stack');
	       halt;
	    end;
	 TopRator := RatorHead^.rator;
      end;

   { return priority of an operator, higher values mean higher precedence }
   function priority(op : operator) : integer;
      begin
	 case op of
	 plus, minus : priority := 1;
	 times       : priority := 2;
	 end;
      end;
   
   { Read in an operand which must be a simple number }
   function ReadRand : eptr;
      var
	 NewRand : eptr;
      begin
	 if eoln
	 then
	    begin
	       writeln('Bad input: Expected number, got end of line');
	       halt;
	    end;
	 new(NewRand);
	 NewRand^.eexptype := number;
	 read(NewRand^.evalue);
	 ReadRand := NewRand;
	 if debug then writeln('ReadRand gets ', NewRand^.evalue);
      end;

   { Read in an operator }
   function ReadRator : operator;
      var
	 ch : char;
	 result : operator;
      begin
	 { get a character, skipping spaces }
	 repeat
	    if eoln
	    then
	       begin
		  writeln('Bad input: Expected operator, got end of line');
		  halt;
	       end;
	    read(ch);
	 until ch <> ' ';

	 if not (ch in ['+', '-', '*'])
	 then
	    begin
	       writeln('Bad input: Expected operator, found "', ch, '".');
	       halt;
	    end
	 else
	    case ch of
	    '+':
	       result := plus;
	    '-':
	       result := minus;
	    '*':
	       result := times;
	    end;
	 ReadRator := result;
	 if debug then writeln('ReadRator gets "', ch, '"');
      end;

   function ReadExpression:eptr;
      var
	 endexpr : boolean;   { have we got to the last operand on the line? }
	 done    : boolean;   { hack around pascal's nasty while loops }
	 NewRator : operator; { the operator we just read in }
	 NewExp   : eptr; { new expression node under construction }
      begin
	 initstacks;
	 endexpr := false;
	 repeat
	    PushRand(ReadRand);
	    if eoln
	    then
	       endexpr := true
	    else
	       begin
		  NewRator := ReadRator;

		  done := false;
		  while not EmptyRator and not done do
		     if priority(TopRator) >= priority(NewRator)
		     then
			begin
			   new(NewExp);
			   NewExp^.eexptype      := subexpression;
			   NewExp^.eoperator     := PopRator;
			   NewExp^.erightoperand := PopRand;
			   NewExp^.eleftoperand  := PopRand;
			   PushRand(NewExp);
			end
		     else
			done := true;
		  PushRator(NewRator);
	       end;
	 until endexpr;
	 readln;

	 { process all the pending operators. }
	 while not EmptyRator do
	    begin
	       new(NewExp);
	       NewExp^.eexptype      := subexpression;
	       NewExp^.eoperator     := PopRator;
	       NewExp^.erightoperand := PopRand;
	       NewExp^.eleftoperand  := PopRand;
	       PushRand(NewExp);
	    end;

	 { and return the one remaining operand node }
	 ReadExpression := PopRand;

	 { Of course my code always works, but I'll just check... }
	 if not EmptyRand or not EmptyRator
	 then
	    begin
	       writeln('Panic! Stacks not empty at end of readexpression!');
	       halt;
	    end;

      end;

   { Make main a sub-function so that its local variables are not accessible to
      all the other sub-functions. }
   begin
      readexpression := ReadExpression;
   end;

{ function evaluate(expr:eptr):integer; goes here }

begin
   debug := false;
   while not eof do
      writeln ( evaluate ( readexpression ) );
end.