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

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?

From stackoverflow kanske

• 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.

  From Lasse V. Karlsen

• 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.

  From Konrad Rudolph

• 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.

  From Greg Hewgill