Search code examples
mathpostfix-notationunary-operatorrpn

How do unary operators get parsed using RPN?


Given the infix expression -190 + 20, what would the correct result look like as RPN?

-190 + 20 == -190 20 + ?

or..

-190 + 20 == 190 - 20 + ?

Are the rules for unary operators (negative) the same as other operators, but just a right associative property, and higher priority?

Similarly an expression like: -(9 + 9)

Would be? -(9 + 9) = 9 - 9 +?


Solution

  • In a typical RPN language, you can't have the same token - interpreted as either a unary or binary operator depending on context, because there is no context. It has to always be one or the other. So commonly - is kept as the binary subtraction operator, and some other token is used for the unary negation operator. Forth, for instance, called it NEGATE. Thus in Forth, your -190 + 20 could be coded as 190 NEGATE 20 +, and your -(9+9) as 9 9 + NEGATE.

    Forth could also parse negative numbers, so your -190 + 20 could also be coded -190 20 +. However the - is not an operator in this instance, but merely part of the single token -190. The only operator being used in this example is +.

    If you write 190 - 20 + in a typical RPN language, you will get a stack underflow (or else whatever happened to be on the stack, minus 190, plus 20) since - is unconditionally interpreted as the binary operator.

    RPN has no concept of precedence nor associativity - those serve to resolve ambiguity in the evaluation of expressions, and RPN has no such ambiguity in the first place.