[FOM] Formal grammar question

[Todd Wilson]

A.P. Hazen wrote:
> At least the obvious intuitive way of checking Polish formulas
> involvesd more back-and-forthing.  Is this essential?

You can evaluate Polish expressions using a stack, as its done on the 
old HP calculators, or in the Forth programming language, or in 
PostScript (the printer language/file format): starting from the left 
and proceeding to the right, every time you read an operand, push it 
onto the stack, and every time you read an n-ary operator, pop n 
arguments from the stack, perform the operation, and push the result 
back on.  Without actually doing the operations, you can check 
well-formedness simply by keeping track of the stack size as you move 
across the formula, making sure that it is always non-negative, and 
checking that it is equal to 1 at the end.

--
Todd Wilson                               A smile is not an individual
Computer Science Department               product; it is a co-product.
California State University, Fresno                 -- Thich Nhat Hanh