5

I understand how to convert infix to postfix/prefix but I do not understand why postfix or prefix expression are used in computer system?

What is the advantage of postfix prefix over infix expression?

gnat
  • 21,442
  • 29
  • 112
  • 288
Joydip Ghosh
  • 77
  • 1
  • 1
  • 3
  • [Sharing your research helps everyone](http://meta.programmers.stackexchange.com/questions/6559/why-is-research-important). Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see [ask] – gnat Aug 29 '15 at 18:54
  • 6
    Because prefix and postfix expressions can often be processed by a trivial stack-based algorithm, and they never require parentheses, order of operations or associativity rules for disambiguation. It's not hard to find websites explaining this in great detail. – Ixrec Aug 29 '15 at 19:14

2 Answers2

13

Both pre- and postfix have basically the same advantages over infix notation. The most important of these are:

  • much easier to translate to a format that is suitable for direct execution. Either format can trivially be turned into a tree for further processing, and postfix can be directly translated to code if you use a stack-based processor or virtual machine

  • entirely unambiguous. Infix notation requires precedence and associativity rules to disambiguate it, or addition of extra parentheses that are not usually considered part of the notation. As long as the number of arguments to each operator are known in advance, both prefix and postfix notation are entirely unambiguous: "* + 5 6 3" is (5+6)*3, and cannot be interpreted as 5+(6*3), whereas parenthesis is required to achieve with infix.

  • supports operators with different numbers of arguments without variation of syntax. "unary-op 5" and "ternary-op 1 2 3" both work fine, but need special syntax to make them work in infix.

Jules
  • 17,614
  • 2
  • 33
  • 63
3

Notice that LISP languages (e.g. Common Lisp, Scheme, Clojure and many specific dialects inspired by them like AutoLISP, Emacs-LISP, MELT, etc...) are all using a prefix-syntax: every expression starts with a left parenthesis, then the operator, then the operands, then the right parenthesis. These expressions are called S-expressions. For example 1+2*3 is typed as (+ 1 (* 2 3)) and there is no need for operator precedence.

The advantages of such a simple syntax (probably the simplest possible one for ASTs, outside of stack languages à la Forth) include:

  • easy to remember syntax rule for human developers
  • easy and quick to parse for language implementations
  • easy to emit when generating code in s-expressions (from some AST representation)
  • ability to easily make homoiconic languages above them
  • ability to handle many operands (e.g. have variadic operators or functions, or functions with many formal arguments)
  • simple to read, once you can match a left parenthesis with its right one

The disadvantage of such syntax is a pun on the language: Lots of Insipid Stupid Parenthesis. However (believe it or not) any Lisp coder don't see the parenthesis as agressive, and uses the ability (provided by any good editor) to match parenthesis when reading code on the screen.

BTW, what is important is not to convert textual representation from e.g. infix to prefix, but to parse expressions into AST (abstract syntax trees). Very often, an AST is a tree-like structure in memory, keeping more information that the simple syntactical shape (e.g. the source location, as a file name, line number, column number, or some type information, etc...).

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125