RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Taming Trees: Parsing and Sorting

Learn how to use parse trees to evaluate mathematical expressions, and how to use sorted trees.

he first part of this series explained basic tree terminology and showed how to build a simple binary tree in Visual Basic or C#. It also explained how to perform traversals of trees but the only really practical application it showed was how to make a tree draw itself. That’s pretty handy if you need to display a tree, but trees can do so much more.

This article explains a few more practical uses for trees. First, it explains how to use a tree to parse arithmetic expressions. It then discusses sorted trees and shows how to use a sorted tree to build a simple animal guessing game.

Evaluating Expressions
You can represent an arithmetic expression such as -2*(8+7)/-10 with an expression tree or parse tree. Interior nodes in the tree represent operands such as *, ( ), and /. Leaf nodes represent numbers such as 2, 80, and 3.14159265.

Figure 1. Expressive Trees: This tree represents the expression -2*(8+7)/-10.
The value of a leaf node is simply the value of its number. To get the value of a non-leaf node, you calculate the values of its children and then combine them by using the appropriate operation.

For example, Figure 1 shows the parse tree for the expression -2*(8+7)/-10. The values of the two lowest nodes are 8 and 7. The value of their parent node is 8 + 7. If you work through the entire tree, you’ll find that the value of the root node is 3.

Making a parse tree evaluate itself is easy. The node class’s Evaluate function simply calls its children’s Evaluate function and then combines the results by using the appropriate operand. (More on this later.)

The tricky part is building the parse tree; you need to pick apart the expression and figure out what nodes to build to represent the expression’s pieces.

The example program EvaluateExpressions, which is available for download in Visual Basic and C# versions, uses an ExpressionNode class to represent the pieces of an expression. This class uses four variables to keep track of the sub-expression that it represents. Expression stores a string representing the node’s sub-expression. LeftChild and RightChild are references to ExpressionNode objects, which represent the node’s children in the tree. Op holds the node’s operand.

For example, the root node in Figure 1 has Expression = “-2*(8+7)/-10” and Op = “/”. The following code shows the ExpressionNode class's constructor. The code saves the node’s expression and sets its children to Nothing. It then calls the ParseExpression method to do all of the fun work.

' Constructor.
Public Sub New(ByVal new_expression As String)
  ' Build the expression's parse tree.
  Expression = new_expression
  LeftChild = Nothing
  RightChild = Nothing
End Sub
Listing 1 shows the ParseExpression method. It’s fairly long and a little tricky, but here’s the general idea.

If you look again at the parse tree shown in Figure 1, you’ll see that the topmost node represents the last operator that should be applied when evaluating the expression. The node’s children represent the left and right operands for that operator.

To understand how this works, you first need a little background. The basic idea is to scan through the expression looking for the operator that should be evaluated last, create child nodes to represent the operands, and then make the children recursively parse their sub-expressions.

The trickiest part is figuring out which operator should be evaluated last, which is logically the place where you want to break up the expression.

To determine which operator should be evaluated last, the program uses the notion of precedence. An operator’s precedence determines whether it has priority over other operators. For example, normally when you evaluate an expression such as 2+3*4, multiplication has higher precedence than addition, so you perform the multiplication first. That means this expression is equivalent to 2+(3*4).

The ExpressionNode class uses the same precedence rules as Visual Basic and C#. The following table shows operator precedence in decreasing order. For example, unary + and – have the highest precedence, so they are evaluated first.

Table 1. Operator precedence: The table shows operator precedence in decreasing order
+, -
Unary plus, unary minus
*, /
Multiplication, division
Integer division
+, -
Addition, subtraction

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date