Can all RPN expressions be represented such that all operators appear on the left and all operands appear on the right?

Question

I've convinced myself that they can't.

Take for example:

4 4 + 4 /

stack: 4 stack: 4 4 4 + 4 = 8 stack: 8 stack: 8 4 8 / 4 = 2 stack: 2

There are two ways that you could write the above expression with the same operators and operands such that the operands all come first: "4 4 4 + /" and "4 4 4 / +", neither of which evaluate to 2.

"4 4 4 + /" stack: 4 stack: 4 4 stack: 4 4 4 4 + 4 = 8 stack: 4 8 4 / 8 = 0.5 stack: 0.5

"4 4 4 / +" stack: 4 stack: 4 4 stack: 4 4 4 4 / 4 = 1 stack: 4 1 4 + 1 = 5 stack: 5

If you have the ability to swap items on the stack then yes, it's possible, otherwise, no.

Thoughts?

Answer 1

It is enough to show one that can't in order to tell you the answer to this.

If you can't reorder the stack contents, then the expression (2+4)*(7+8) can't be rearranged.

2 4 + 7 8 + *

No matter how you reorder this, you'll end up with something that needs to be summed before you go on.

At least I believe so.

Answer 2

Actually, you've not only given the answer but a conclusive proof as well, by examining a counter-example which is enough to disprove the assumption implied in the title.

Answer 3

Consider the algebraic expression:

(a + b) * (c + d)

The obvious translation to RPN would be:

a b + c d + *

Even with a swap operation available, I don't think there is a way to collect all the operators on the right:

a b c d +
a b S

where S is the sum of c and d. At this point, you couldn't use a single swap operation to get both a and b in place for a + operation. Instead, you would need a more sophisticated stack operation (such as roll) to get a and b in the right spot. I don't know whether a roll operation would be sufficient for all cases, either.