Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Prefix Notation

In prefix notation  the operator is written before its operands. Therefore, in order to print the prefix expression from an expression tree, preorder traversal is done. That is, at every non-terminal node we do the following:

  1. Print the root; and then
  2. print a left parenthesis; and then
  3. traverse the left subtree; and then
  4. print a comma; and then
  5. traverse the right subtree; and then
  6. print a right parenthesis.
If we use this procedure to print the tree given in Figure gif we get the prefix expression

  equation15432

While this notation may appear unfamiliar at first, consider the result obtained when we spell out the names of the operators: 

Plus(Div(a,b), Times(Minus(c,d), e))
This is precisely the notation used in a typical programming language to invoke user defined methods Plus, Minus, Times, and Div.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.