Why postfix (rpn) notation is more used than prefix?

Question

By use I mean its use in many calculators like HP35-

My guesses (and confusions) are -

1. postfix is actually more memory efficient -( SO post comments here ). (confusion - The evaluation algorithm of both are similar with a stack)
2. keyboard input type in calculators back then(confusion - this shouldn't have mattered much as it only depends on order of operators given first or last)

Another way this question can be asked is what advantages postfix notation have over prefix?
Can anyone enlighten me?

Ute

Answer 1

For one it is easier to implement evaluation.

With prefix, if you push an operator, then its operands, you need to have forward knowledge of when the operator has all its operands. Basically you need to keep track of when operators you've pushed have all their operands so that you can unwind the stack and evaluate.

Since a complex expression will likely end up with many operators on the stack you need to have a data structure that can handle this.

For instance, this expression: - + 10 20 + 30 40 will have one - and one + on the stack at the same time, and for each you need to know if you have the operands available.

With suffix, when you push an operator, the operands are (should) already on the stack, simply pop the operands and evaluate. You only need a stack that can handle operands, and no other data structure is necessary.

Brittani

Look if I evaluate the prefix-notation from right-to-left, I do not need any operator in stack. From right, - + 10 20 (+ 30 40) evaluating the part indicated by braces to - + 10 20 70 . Now pushing 70 to stack. And evaluating, -(+ 10 20) 70 while 70 on stack, to - 30 70 . Finally evaluating the rest of it to -40. – Berar

Answer 2

Prefix notation is probably used more commonly ... in mathematics, in expressions like F(x,y). It's a very old convention, but like many old systems (feet and inches, letter paper) it has drawbacks compared to what we could do if we used a more thoughtfully designed system.

Just about every first year university math textbook has to waste a page at least explaining that f(g(x)) means we apply g first then f. Doing it in reading order makes so much more sense: x.f.g means we apply f first. Then if we want to apply h "after" we just say x.f.g.h.

As an example, consider an issue in 3d rotations that I recently had to deal with. We want to rotate a vector according to XYZ convention. In postfix, the operation is vec.rotx(phi).roty(theta).rotz(psi). With prefix, we have to overload * or () and then reverse the order of the operations, e.g., rotz*roty*rotx*vec. That is error prone and irritating to have to think about that all the time when you want to be thinking about bigger issues.

For example, I saw something like rotx*roty*rotz*vec in someone else's code and I didn't know whether it was a mistake or an unusual ZYX rotation convention. I still don't know. The program worked, so it was internally self-consistent, but in this case prefix notation made it hard to maintain.

Another issue with prefix notation is that when we (or a computer) parses the expression f(g(h(x))) we have to hold f in our memory (or on the stack), then g, then h, then ok we can apply h to x, then we can apply g to the result, then f to the result. Too much stuff in memory compared to x.f.g.h. At some point (for humans much sooner than computers) we will run out of memory. Failure in that way is not common, but why even open the door to that when x.f.g.h requires no short term memory. It's like the difference between recursion and looping.

And another thing: f(g(h(x))) has so many parentheses that it's starting to look like Lisp. Postfix notation is unambiguous when it comes to operator precedence.

Some mathematicians (in particular Nathan Jacobson) have tried changing the convention, because postfix so much easier to work with in noncommutative algebra where order really matters, to little avail. But since we have a chance to do things over, better, in computing, we should take the opportunity.

Pastiche

Answer 3

Basically, because if you write the expression in postfix, you can evaluate that expression using just a Stack:

1. Read the next element of the expression,

2. If it is an operand, push into Stack,

3. Otherwise read from Stack operands required by the Operation, & push the result into Stack.

4. If not the end of the expression, go to 1.

Example

expression = 1 2 + 3 4 + *
stack = [  ]

Read 1, 1 is Operand, Push 1
[ 1 ]

Read 2, 2 is Operand, Push 2
[ 1 2 ]

Read +, + is Operation, Pop two Operands 1 2
Evaluate 1 + 2 = 3, Push 3
[ 3 ]

Read 3, 3 is Operand, Push 3
[ 3 3 ]

Read 4, 4 is Operand, Push 4
[ 3 3 4 ]

Read +, + is Operation, Pop two Operands 3 4
Evaluate 3 + 4 = 7, Push 7
[ 3 7 ]

Read *, * is Operation, Pop two Operands 3 7
Evaluate 3 * 7 = 21, Push 21
[ 21 ]

Knotty

How is it different than Prefix notation like, * + 4 3 + 2 1 ,when evaluated right-to-left. – Berar

Answer 4

If you like your human reading order to match the machine's stack-based evaluation order then postfix is a good choice.

That is, assuming you read left-to-right, which not everyone does (e.g. Hebrew, Arabic, ...). And assuming your machine evaluates with a stack, which not all do (e.g. term rewriting - see Joy).

On the other hand, there's nothing wrong with the human preferring prefix while the machine evaluates "back to front/bottom-to-top". Serialization could be reversed too if the concern is evaluation as tokens arrive. Tool assistance may work better in prefix notation (knowing functions/words first may help scope valid arguments), but you could always type right-to-left.

It's merely a convention I believe...

Quinby

Answer 5

Offline evaluation of both notation is same in theoretical machine

(Eager evaluation strategy)Evaluating with only one stack(without putting operator in stack)

It can be done by evaluating Prefix-notation right-to-left.

- 7 + 2 3
# evaluate + 2 3
- 7 5
# evaluate - 7 5
2

It is same as evaluating Postfix-notation left-to-right.

7 2 3 + -
# put 7 on stack
7 2 3 + -
# evaluate 2 3 +
7 5 -
# evaluate 7 5 -
2

(Optimized short-circuit strategy) Evaluating with two stacks(one for operator and one for operand)

It can be done by evaluating Prefix-notation left-to-right.

|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# push < 2 3 in stack
instruction-stack: or, less_than
operand-stack: 1, 2, 3
# evaluate < 2 3 as 1
instruction-stack: or
operand-stack: 1, 1
# evaluate || 1 1 as 1
operand-stack:1

Notice that we can do short-circuit optimization for the boolean expression here easily(compared to previous evaluation sequence).

|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# Is it possible to evaluate `|| 1` without evaluating the rest ? Yes !!
# skip < 2 3 and put place-holder 0
instruction-stack: or
operand-stack: 1 0
# evaluate || 1 0 as 1
operand-stack: 1

It is same as evaluating Postfix-notation right-to-left.

(Optimized short-circuit strategy) Evaluating with one stack that takes a tuple (same as above)

It can be done by evaluating Prefix-notation left-to-right.

|| 1 < 2 3
# put || 1 in tuple-stack
stack tuple[or,1,unknown]
< 2 3
# We do not need to compute < 2 3
stack tuple[or,1,unknown]
# evaluate || 1 unknown as 1
1

It is same as evaluating Postfix-notation right-to-left.

Online evaluation in a calculator while human entering data in left-to-right

When putting numbers in a calculator, the Postfix-notation 2 3 + can be evaluated instantly without any knowledge of the symbol human is going to put. It is opposite of Prefix notation because when we have - 7 + we have nothing to do, not until we get something like - 7 + 2 3.

Online evaluation in a calculator while human entering data in right-to-left

Now the Prefix-notation can evaluate + 2 3 instantly, while the Postfix-notation waits for further input when it has 3 + - .

Please refer to @AshleyF note that the Arabic-language writes from right-to-left in contrast to English-language that writes from left-to-write !

I guess little-endian and big-endian is something related to this prefix/postfix notation.

One final comment, Reverse-Polish notation is strongly supported by Dijkstra (he is strong opponent of short-circuit optimization and regarded as the inventor of Reverse-Polish notation). It is your choice to support his opinion or not(I do not).

Berar