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


Taming Trees: Parsing and Sorting : Page 2

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

Evaluating Expressions (cont'd)
If two operators have the same precedence, they are evaluated in left-to-right order. For example, the expression 2*3*4 is treated as (2*3)*4. (Note that in those cases it doesn’t really matter because multiplication is associative so (2*3)*4 = 2*(3*4) anyway.)

So the code scans through the expression looking for the operator with the lowest precedence to use as the dividing point. It counts opening and closing parentheses as it goes so it knows when it is not inside any parentheses (the operator with the lowest precedence cannot be inside any parentheses).

The code needs to handle a few special cases, such as telling the difference between unary +/– and addition/subtraction, expressions that are surrounded by parentheses such as (1+2), functions such as Sin(2/3) and Factorial(3*2), and literal values such as 0.11235.

After it finds the dividing operator, the code stores the node’s operator in its Op variable, creates two child nodes, and makes the children recursively parse their sub-expressions. See the code in Listing 1 for the details.

After you parse an expression, evaluating it is easy. The following code shows part of the ExpressionNode class’s Evaluate function. The node checks its Op variable. If Op is blank, then the node represents a literal value so the code returns that value converted into a Double.

If Op is not blank, then the node represents an expression. The code uses a Select Case statement to see which operator it represents. It recursively makes the child nodes evaluate their values and then combines the results appropriately, as shown in the code below.

Figure 2. Evaluate This: The EvaluateExpression program uses the ExpressionNode and ExpressionTree classes to evaluate expressions.

' Evaluate the parsed tree. Public Function Evaluate() As Double ' See if we have an operand. If Op = "" Then ' No operand. This is a literal. Return Double.Parse(Expression) Else ' See what the operand is. Select Case Op.ToLower() Case "^" ' Power. Return LeftChild.Evaluate() ^ RightChild.Evaluate() Case "*" ' Times. Return LeftChild.Evaluate() * RightChild.Evaluate() ... Code omitted ... Case "sin" ' Sine. Return Sin(LeftChild.Evaluate()) ... More code omitted ... End Select End If End Function

Figure 2 shows the EvaluateExpression program in action. The drawing code included in the ExpressionNode class displayed the parse tree (this code is similar to the code described in the first part of this series).

If you take out the drawing code, the ExpressionNode and ExpressionTree classes can evaluate arithmetic expressions pretty quickly. If you need to evaluate expressions on the fly, they work quite well.

With a little extra work, you can make a few useful variations on these classes. For example, you could allow a leaf node to hold a variable such as A or B. Then, when you evaluate the expression, you can look up variable values in a dictionary. For example, you could use a tree to solve A*Sin(X^2+Y^2) for specific values of A, X, and Y. If you need to perform this same calculation for a lot of different A, X, and Y values, you can save time by building the tree once and then evaluating it a bunch of times with a different variable dictionary.

Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



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