Why postfix arithmetic expression is not ambiguous?

Question

A binary tree can be written as an expression, no matter prefix, postfix or infix.
But why an infix expression needs brackets, while the others don't?

Say, why postfix, prefix produce only one binary tree, while infix can produce many (and become ambiguous)?

I'm looking for a formal proof...

Answer 1

With operator precedence infix is not ambiguous. Brackets are a convenience but not necessary to form an expression. However when parsing you have to resolve each precedence level in precedence order (e.g., $^,[*,/],[+,-]$).

A postfix expression is written exactly in computation order: $e0\ e1\ o1\ ... (ek\ ok) ... eN\ oN$ Computation is

• $r[1] = o1(e0,e1)$
• ...
• $rk = ok(r[k-1],ek)$
• ...
• $rN = oN(r[N-1],eN)$

Infix is subjectively thought by many to be easier for humans to read and write.

There is no reason why brackets couldn't be added to postfix or prefix with the obvious meaning, but it is generally not done as those formats are intended for machines rather than humans.