Search code examples
rpn

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?


Solution

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