[FOM] Formal grammar question
twilson at csufresno.edu
Tue Nov 8 23:54:53 EST 2005
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
More information about the FOM