CodePlexProject Hosting for Open Source Software

This is an article on how to build a basic expression evaluator. It can evaluate any numerical expression combined with trigonometric functions for now. Constants like e and pi are also supported.

Background

Operator Precedence

I will explain the Regular Expressions part required here

The Code

IsNumeric and IsFunct are functions which check if the character is numeric and the latter is a custom function that checks if the character responds to one of the symbols corresponding to a function.

tokens.Items.Clear() 'Remove all spaces expr.Text = Replace(expr.Text, " ", "") Dim num As String, op As Char num = "" op = "" Dim x As New System.Text.RegularExpressions.Regex("[0-9]\-[0-9]") For Each abc As System.Text.RegularExpressions.Match In x.Matches(expr.Text) Dim l = CDbl(abc.Value.Split("-")(0)) Dim r = CDbl(abc.Value.Split("-")(1)) expr.Text = Replace(expr.Text, abc.Value, l & "+-" & r) Next 'Sin : ~ 'Cos : ` 'Tan : ! 'Sec : @ 'Cosec or Csc : # 'Cot : $ expr.Text = Replace(LCase(expr.Text), "sin", "~") expr.Text = Replace(LCase(expr.Text), "cos", "`") expr.Text = Replace(LCase(expr.Text), "tan", "!") expr.Text = Replace(LCase(expr.Text), "sec", "@") expr.Text = Replace(LCase(expr.Text), "csc", "#") expr.Text = Replace(LCase(expr.Text), "cosec", "#") expr.Text = Replace(LCase(expr.Text), "cot", "$") expr.Text = Replace(LCase(expr.Text), "pi", Math.Round(Math.PI, 4)) expr.Text = Replace(LCase(expr.Text), "e", Math.Round(Math.Exp(1), 4)) 'e^1 or e For Each s As Char In expr.Text If IsNumeric(s) Or s = "."c Or s = "-" Or IsFunct(s) Then num = num & s End If If IsOp(s) Then op = s tkns.Add(num) tkns.Add(op) op = "" num = "" End If Next 'The last number will not be stored because there is no operator next to it tkns.Add(num) 'Display In ListBox tokens.Items.Clear() For Each Str As String In tkns tokens.Items.Add(Str) Next

The first term you need to know when you are trying to evaluate expressions is "tokenize". It means splitting into simpler parts. For example, "12+5*3" is tokenized to "12","+","5","*" and "3"

Before tokenizing, I thought I would do some substitutions to make it simpler for the programmer.

First, we should replace all the spaces with no character to avoid errors like "Cannot convert " " to Double".

Secondly, treating '-' as an operator might lead into few complications because when you are giving expressions like "5*-5", the logic we have provided here will get complicated. So, to support negative numbers with our simple logic, the easiest workaround would be replacing all instances of the form "number-number" with "number+-number".

While tokenizing, we write a logic such that the - sign is also concatenated to the string.

We use Regex to do this. I will explain about it later.

Then, I replace functions with symbols. For example, the trigonometric function Sine is replaced with "~". So, when I want to evaluate the expression, I can recognize the "~" symbol and evaluate Sine(the number following it). How I'm doing it will be mentioned in the explanation of the Evaluation part.

Then, I have replaced PI and e with their respective values rounded to 4 decimal digits. One thing to be noticed here is, the user might accidentally type "Pi" or "pI" or "PI". So, in order to handle substitutions in general, better use the LCase function and search for the replacement string ("pi" in this case) in lower case.

The logic I've been mentioning all along is is :

* Read character by character in the expression.

* If the character is a number or a dot or a '-' sign or a symbol denoting a function(like "~" for sine), concatenate it to a string.

* If it is an operator, add the number to a list followed by the operator. Set the values of the number string and the operator string to be "".

* After the loop is over, add the number in the string(num in this case) to the list because, there will be no operator in the end.

Then clear the ListBox tokens and add all the entries in the list (tokens in this case) so that the user can see how it is tokenized. It is not necessary to include the ListBox in all expression evaluators. This is just to see if the program properly tokenizes the expression.

Dim x As New System.Text.RegularExpressions.Regex("[0-9]\-[0-9]") For Each abc As System.Text.RegularExpressions.Match In x.Matches(expr.Text) Dim l = CDbl(abc.Value.Split("-")(0)) Dim r = CDbl(abc.Value.Split("-")(1)) expr.Text = Replace(expr.Text, abc.Value, l & "+-" & r) Next

Coming back to to RegEx or Regular Expressions, one can say that it is very useful in pattern matching. Here, the pattern we are trying to match is of the form "a numerical digit-a numerical digit". Lets take the expression "12-3+15-4"

The matches returned by Regex will be "2-3" and "5-4". Then, we can replace it with "2

In the declaration of x, I have given "0-9\-0-9" as the Pattern string. This pattern string is what the regex finds as matches. The pattern string here means "Any digit from zero to nine-any digit from zero to nine". One or more characters within the "[]" will be matched and the "\-" means - should be treated as a "-" character and not as what it is meant to be in the Regex syntax. Normally, the "-" is used inside the "[]" to denote a range like "0-9" or "a-z" or "A-Z". "\" is called an escape sequence that forces the next character to be treated as a literal.

Private Function EvalFunction(ByVal s As String) As Double If Not IsFunct(s.Chars(0)) Then 's.chars(0) is the function symbol Return CDbl(s) End If Dim z As Double = CDbl(s.Substring(1, s.Length - 1)) ' Leaves the operator and retrieves the number 'z is an angle in degrees. To use it directly in the Math.Sin or Math.Cos etc. functions, we give radian values '180 degrees PI radians 'z degrees z * PI/180 z = z * Math.PI / 180 Select Case s.Chars(0) Case "~" Return Math.Sin(z) Case "`" Return Math.Cos(z) Case "!" Return Math.Tan(z) Case "@" Return 1 / (Math.Cos(z)) Case "#" Return 1 / (Math.Sin(z)) Case "$" Return 1 / (Math.Tan(z)) End Select End Function

This function is for evaluating strings like "~30"(sin 30) etc. As I have already mentioned, the symbols I have used will always be present in the first character of the string. So, I check if the first character of the string(s here) passed is a symbol in that list. If it is not, I return the same string passed as it is. On the other case, I retrieve the number part using the substring function and convert it to Degrees. The trigonometric functions will treat the value passed as radians. So, I convert the number to degrees. The conversion is like direct proportion. PI Radians equal 180 degrees. How many degrees equal z radians?

So, z = z * PI/180

Then, the respective function is performed on z and is returned by checking all possible symbols that can be present as the first character of s.

'Evaluate all functions For i As Integer = 0 To tkns.Count - 1 Dim s = tkns(i) If TypeOf s Is Char Then If IsFunct(s) Then tkns.Item(i) = EvalFunction(s) End If Else If IsFunct(s.chars(0)) Then tkns.Item(i) = EvalFunction(s) End If End If Next 'Exponentiation Dim ind = tkns.IndexOf("^"c) While Not (ind < 0) 'If there is no such string in the list, it will return -1 Dim lhs = CDbl(tkns(ind - 1)) Dim rhs = CDbl(tkns(ind + 1)) Dim res = lhs ^ rhs tkns.Insert(ind, res) tkns.RemoveAt(ind - 1) tkns.RemoveAt(ind + 1) tkns.RemoveAt(ind) ind = tkns.IndexOf("^"c) End While

First, we evaluate the functions. Then, we go to the operators.

The logic for an operation is :

* Get the first position (or index is better here) of the operator.

* While the operator exists,

o Get the left value and the right value which are located to the left of the operator and the right of the operator respectively.

o Evaluate the result

o Insert the result at the position and remove all the three - left value, right value and the operator.

o Find the position of that operator.

Thats it! We have developed a simple mathematician :)

Points of Interest

Substituting a symbol for the functions made the whole process easier

Treating Subtraction as the Addition of a negative number too was good.

Using Regular Expressions. If you want to learn more about Regex, you can visit this website for a simple, yet a good source of learning Regex

http://www.zytrax.com/tech/web/regex.htm

Last edited May 29, 2010 at 12:08 AM by AnshulR, version 4