Data Structures and Algorithms with Object-Oriented Design Patterns in C++

# Expression Trees

Algebraic expressions such as

have an inherent tree-like structure. For example, Figure  is a representation of the expression in Equation . This kind of tree is called an expression tree  .

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the operators (+, -, , and ). Notice that the parentheses which appear in Equation  do not appear in the tree. Nevertheless, the tree representation has captured the intent of the parentheses since the subtraction is lower in the tree than the multiplication.

Figure: Tree representing the expression a/b+(c-d)e

The common algebraic operators are either unary or binary. E.g., addition, subtraction, multiplication and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. I.e., expression trees are usually binary trees.

What can we do with an expression tree? Perhaps the simplest thing to do is to print the expression represented by the tree. Notice that an inorder traversal of the tree in Figure  visits the nodes in the order

Except for the missing parentheses, this is precisely the order in which the symbols appear in Equation !

This suggests that an inorder traversal should be used to print the expression. Consider an inorder traversal which, when it encounters a terminal node simply prints it out; and when it encounters a non-terminal node, does the following:

1. Print a left parenthesis; and then
2. traverse the left subtree; and then
3. print the root; and then
4. traverse the right subtree; and then
5. print a right parenthesis.
Applying this procedure to the tree given in Figure  we get

which, despite the redundant parentheses, represents exactly the same expression as Equation .