0
$\begingroup$

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

Improve this question
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\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.