CS231 lecture notes, Fall 1999
Week 8, Monday

Postfix
-------

Stack based evaluation of postfix expressions.

Basic rules for interpreting postfix:

1) see an operand, push it on the stack

2) see an operator, pop two things off the stack and apply
   the operator to them.  Push the result onto the stack

Tricky things:

       1) keeping track of what order to apply the operation
          when you get the two things off the stack
       2) dealing with stack empty errors and such

Examples:

34+    means... push 3 push 4 pop pop add
342*+  means 4*2+3

What does

31- mean?  3-1 or 1-3?

It's 3-1, which implies that when we pop things off the stack,
we pop the SECOND ARGUMENT FIRST!


What are the tools we are going to need to code this up?

1) ability to traverse a string and extract characters and
   (maybe) ranges.
2) ability to identify digits and operators
3) ability to put integers onto a Stack

For each of these things, you should look up the relevant
documentation and test out some simple cases in isolation
until you know what you are doing.

Development plan?


infix to postfix translation
----------------------------

Why does Lafore distinguish between the way people work and the way
the computer works.

1) people search for patterns (like number-operator-number)

2) computers look at only one character at a time

3) people access pages randomly, skipping around a lot

4) the computer proceeds from left to right, once

Single-pass parsing, using no context and only one stack for state,
is the ultimate (well, penultimate) in reductionist interpretation.

Let's explain the algorithm:

Simple version: no parentheses

operand		output it
operator	while (stack not empty)
		      pending = peek ()
	              if current outranks pending, break
		      otherwise pop the pending operator and output it
                push current
end of input	pop and print all remaining operators

Examples:

1+2*3		the current outranks the pending, so the pending doesn't
		get output yet

1*2+3		the current does not outrank the pending, so the pending
		operation can proceed

1+2+3		the current does not outrank the pending, so the pending
		operation can proceed


While reading, there is a notion of a current operation that we are
trying to complete by finding the second argument.  The only problem
is that sometimes the "second argument" is big.

Example:   1+2*3*4*5*6...

Have to keep going until we get to something that does not outrank
addition (like another addition).  Once we do, we have our second
operator:

Example:  1+2*3*4*5*6+...

The second operator in this case is 2*3*4*5*6

Parentheses are another way of making the pending operation wait

Example:  1+(.........)

We're not finished until we find the matching close parenthesis.

How do we do that?  Same way we checked for balancing parenthesis:
push open parens on the stack and pop when we see close parens

Example:  1+(....(...) (...(...)...) ...)

push, push, pop, push, push, pop, pop, pop

Now let's add parentheses to the interpreter.

operand		output it
(		push (
)		while (stack not empty)
		      pending = pop;
		      if pending is a (, break
		      otherwise output pending

operator	while (stack not empty)
		      pending = peek ()
		      if pending is a (, break
	              if current outranks pending, break
		      otherwise pop the pending operator and output it
                push current

end of input	pop and print all remaining operators

1) An opening parenthesis starts a new subexpression by pushing a marker
   onto the stack

2) Hitting a close parenthesis is just like getting to the end of a
string, except that instead of printing the whole stack and then
quitting, we output everything back to the last parenthesis and then
proceed with the rest of the expression.

3) Similarly, when we are popping pending operators, we have to quit
   when we get to an open parenthesis.  This forces us to treat the
   subexpression as a separate entity rather than lumping operations
   from one level with operations from another.


Examples:

	1*(2+3)
	(1+2)*(3+4)
	((1+2)*3)-4

Development plan
----------------

In retrospect, what was my development plan?

1) Started with Eval

2) Found two ways to convert characters to integers:

3) Tested isDigit

4) Wrote isOperator

5) Identified the characters in a String

6) Wrote precedence and outranks

7) Copy a String into a StringBuffer

8) Implement the expression evaluator.  At this point I did an evil
   thing and skipped way too many steps, but I got something that
   mostly worked, although it took a little while to compile:

9) I implemented a simplified version of the translator that doesn't
handle parentheses.

10) Now I went for the whole enchilada (without parentheses).  I took
me a while to untangle the book's presentation of the logic.

11) Then I added parentheses.

12) Last step is to put it all together:

      StringBuffer postfix = translate (infix);
      System.out.println (postfix);
      int res = evaluate (postfix);
      System.out.println (res);