Expression evaluation using Emit
This class was designed to evaluate simple mathematical expressions. But instead of developing a routine to do the calculating, we use Emit to dynamically build a method that does the math for us.
IMPORTANT: This is done with integer math. 7/2*3 = 9, not 10.5 (or even 10)
To use this class first create an instance of the class, then pass a string to the Process method that contains your equation. It will return the value of this expression.
Evaluate e = new Evaluate();
int value = e.Process("1+8*(3-4/5)/7+((23-5)/2)+7)");The main method of this class, Process(), does three things
- Coverts the expression string into tokens
- Converts the infix tokens into postfix
- Generates and executes the dynamic method
public int Process(String input) {
Queue<String> tokens = Tokenize(input);
Queue<String> queue = InfixToPostFix(tokens);
return Eval(queue);
}Generating Tokens
We generate tokens by moving through the string character by character. If the character is one of the symbols we accept, we add it to the queue. But before we add it we make sure we weren't in the process of building a number. Since numbers can span multiple characters we could have finished one and not known it until we encounter a symbol. Thus we test if the StringBuilder has anything in it, and if it does, we add it to the queue before the symbol. If the current character is a whitespace, we ignore it otherwise we throw an exception since we don't know what to do with other characters. Once we run out of characters we again check to see if we were in the process of building a number (hopefully we were, as ending an expression with a symbol will cause issues later).
private Queue<String> Tokenize(String input) {
int p = 0;
Queue<String> tokens = new Queue<string>();
StringBuilder s = new StringBuilder();
while (p < input.Length) {
if (symbols.Contains(input[p])) {
if (s.Length > 0) {
tokens.Enqueue(s.ToString());
s.Clear();
}
tokens.Enqueue(input[p].ToString());
} else if (Char.IsDigit(input[p])) {
s.Append(input[p]);
} else if (Char.IsWhiteSpace(input[p]) == false) {
throw new InvalidDataException(String.Format("I don't know what to do with {0}", input[p]));
}
p++;
}
if (s.Length > 0) {
tokens.Enqueue(s.ToString());
}
return tokens;
}Infix to Postfix
There are plenty of tutorials on how to do this on the web so we won't explain it here.
private Queue<String> InfixToPostFix(Queue<String> input) {
Stack<String> stack = new Stack<string>();
Queue<String> que = new Queue<String>();
while (input.Count > 0) {
String token = input.Dequeue();
if (operators.Contains(token)) {
while (stack.Count > 0 && stack.Peek() != "(") {
if (Precedence(stack.Peek()) >= Precedence(token)) {
que.Enqueue(stack.Pop());
} else {
break;
}
}
stack.Push(token);
} else if (token == "(") {
stack.Push("(");
} else if (token == ")") {
while (stack.Count > 0 && stack.Peek() != "(") {
que.Enqueue(stack.Pop());
}
if (stack.Count > 0) stack.Pop();
} else {
que.Enqueue(token);
}
}
while (stack.Count > 0) {
que.Enqueue(stack.Pop());
}
return que;
}Precedence
The last method is a simple one. It returns a value indicating the precedence of the operators. The higher the value, the higher the precedence. This is used the the Infix to PostFix routine to determine when to place an operator into the queue.
private int Precedence(String s) {
int result = 0;
switch (s) {
case "*":
case "/":
result = 10;
break;
case "+":
case "-":
result = 9;
break;
default:
result = 0;
break;
}
return result;
}Eval
This is the routine that creates the dynamic method. First thing we do is tell the system we want to create a dynamic method named "MyMethod" that is going to return a typeof(int). It has no parameters (null) and is part of the class Evaluate (typeof(Evaluate)).
We next create an ILGenerator to build the method.
Stepping through each token in the postfix queue, we use a case statement to determine which op code needs to be generated. The various math opcodes take the top two values on the stack, perform the operation, then push the result back onto the stack.
At the end we generate a Return opcode. All methods have to end in return, even those that don't return a value.
Once we have the method, we invoke it passing no arguments to it. We cast the returned value into an int and return that from the Eval method.
private int Eval(Queue<String> tokens) {
DynamicMethod dm = new DynamicMethod("MyMethod", typeof(int), null, typeof(Evaluate));
ILGenerator gen = dm.GetILGenerator();
while (tokens.Count > 0) {
int i;
String value = tokens.Dequeue();
switch (value) {
case "+": gen.Emit(OpCodes.Add); break;
case "-": gen.Emit(OpCodes.Sub); break;
case "*": gen.Emit(OpCodes.Mul); break;
case "/": gen.Emit(OpCodes.Div); break;
default:
i = Int32.Parse(value);
gen.Emit(OpCodes.Ldc_I4, i);
break;
}
}
gen.Emit(OpCodes.Ret);
return (int)dm.Invoke(null, null);
}Note that there is no real error checking in the code and that expressions like -1 are not allowed (if you need -1, you need to write (0-1). Mismatched '(', ')' will also cause problems. This is just intended so show some of the power of Emit, not be an total solution :)
Adding a new symbol is fairly simple. You'd need to add it to the operators string, the case statement in the Eval method and the case statement in the Precedence method. If you are feeling bold, try adding the modulus operator '%'.
