3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it safe to assume that in the industry, operations that are commutative are not scrutinized for exact order? $\endgroup$ – Adam-Morgan Feb 15 '15 at 17:38
  • $\begingroup$ I'm not sure the industry is interested in converting infix to postfix. If they do, their guiding principle is probably "whatever works", and may depend on the application. That said, in compilers it is important to maintain the order of an addition of the form $(a+b)+c$, in contradistinction to, say, $a+(b+c)$, for numerical reasons. $\endgroup$ – Yuval Filmus Feb 15 '15 at 18:05
1
$\begingroup$

In my view postfix expressions code trees. This can be done regardless of semantics. One only needs the arity (number of arguments) of each operator. Thus your two postfix expressions code different trees.

<code>4+(5*6)</code> and <code>(5*6)+4</code>

Infix expressions can also be used to denote (binary) trees but then we usually need parentheses to fix the structure. We can do with less parentheses by adding operator precedence and associativity rules for the operators.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.