A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that 4 + (5 * 6) in infix is written 4 5 6 * + in postfix, as opposed to 5 6 * 4 + in postfix? When the second postfix example is translated into infix, the order of the arguments is switched, but should that matter for operators with the commutative property?
Differences in Postfix Syntax
notation;syntax
There are no rules, you make the rules yourself. The rule used in class has the property that the numbers appear in the same order in both expressions. The rule is also pretty natural:$$ T(\alpha \circ \beta) = T(\alpha) T(\beta) \circ $$Here $\alpha$ is an infix expression, $T(\alpha)$ is the translation of $\alpha$, and $\circ$ is a binary operation. The corresponding rule for unary expressions is $T(\circ \alpha) = T(\alpha) \circ$, and there is also a deparenthesizing rule, $T((\alpha)) = T(\alpha)$. If you apply these rules to the expression $4 + (5 * 6)$ you will get $4 \; 5 \; 6 * + $.Keeping the order is important for operations which are not commutative, such as subtraction and division; that's assuming on the convention that $3 \; 2 \; - = 1$ and so on, rather than the other way around.