| |
 |
CS 3723
Programming Languages |
Reverse Polish Notation |
Reverse Polish Notation (RPN):
RPN is a parenthesis-free notation for expressions, in
which each operator comes after (to the right of) its operands.
For example, we might use arithmetic expressions
with operators: + - * / ^, with parentheses ( ), and with
integers, floats (or even identifiers) as operands.
Suppose one wants to evaluate (find the value of) such an expression, say
3+4*5$, or 3*4+5$.
For convenience, all operands are single-digit integers, and the
strings are assumed to have a $ at the end.
This topic of evaluating an arithmetic expression
is often covered in beginning programming or in data structures.
The method used is a combination of two algorithms:
- Translate an arithmetic expression to RPN.
In the examples above, to 345*+$, and to 34*5+$, and
- Evaluate the RPN.
In the first example,
push the first three operands on a stack, use * on the the top
two operands to get 4*5=20, and push this.
Then use + on the remaining top two operands
(there are only two) to get 3+20=23, getting the final result.
With the second example, push the first two operands, apply * to
the top two operands (there are only two), getting 12 on the stack.
then push the remaining operand 5 on the stack, and apply +
to both stack elements to get 12+5=17.
The second (evaluation) algorithm is much the easier of the two.
In general, the evaluation of RPN input can proceed as follows:
Use an evaluation stack. Proceed through the RPN
from left to right. Operands are
pushed onto the stack, and operators pop their arguments off the
stack and push the result. When a final $ is encountered,
to indicate the end of the input,
the remainder of the stack is popped and printed. (It should
just be a single value.)
The first (translation) algorithm is a lot harder and is usually
what is called an "ad-hoc" algorithm, meaning "for the particular
end or case at hand without consideration of wider application."
We will see that our ability to write a parser for arithmetic
expressions will make the translation in that case completely trivial.
(The ad-hoc parsing method often used is a variation of
operator precedence parsing, which is a poor and
outmoded method.)
As an example (which we will use later), suppose operands are
single digits, and suppose the
arithmetic expression and corresponding RPN are:
- Arith. Expr.:
((3^2 - 4*1*2)^(1/2) - 3)/(2*1)$.
- Corresp. RPN:
32^41*2*-12/^3-21*/$.
Notice that the "32" at the start of the RPN consists of
two operands: a "2" followed by a "3", since all operands in this
example are single digits. The particular expression
here gives the solution to the quadratic equation
y = x^2 + 3x + 2, if everything is evaluated as a float.
Given an arithmetic expression, the corresponding RPN is
uniquely determined if one assume the operands of both parts
occur in the same order. This is the case for the examples above.
(Revision date: 2014-09-16.
Please use ISO 8601,
the International Standard Date and Time Notation.)
|