Dynamic evaluation of an expression

In this post, I'll tackle Step#2 of evaluating an expression like 2 * (3 + 5) and return 16.
  1. Convert expression from infix to postfix (see the last 2 posts)
  2. Evaluate postfix expression to determine result
As always, write a new test for ExpressionConverter

public void TestEvaluate()
ExpressionConverter converter = new ExpressionConverter();
Assert.AreEqual(10, converter.EvaluateInfixExpression("((1+2) + 3) * 8/4"));

The implementation is very simple now that we have the ability to 'convert to postfix'.

public object EvaluateInfixExpression(string sInfixExpression)
List<object> postfixExpression = this.ConvertInfixToPostfix(sInfixExpression);
Stack<object> stack = new Stack<object();
foreach (object term in postfixExpression)
if (term is int)
Operator operatorTerm = term as Operator;
int iValue2 = (int) stack.Pop();
int iValue1 = (int) stack.Pop();
stack.Push( operatorTerm.Evaluate(iValue1, iValue2) );
return stack.Peek();

Except that we don't have Operator#Evaluate()... Lets get over that hurdle. Mark this test with a temp Ignore tag. Write a new test in the TestOperator fixture

public void TestPlusOperator_Evaluate()
Assert.AreEqual(30, Operator.Plus.Evaluate(10, 20));

If each operator could have a associated evaluate code block that evaluated 2 parameters and returned the result, we'd be done. A new member variable, a new parameterized ctor and a new code block later.. Here are the changes

public class Operator
public static readonly Operator Plus = new Operator("+", 1, (x, y) => x + y );
private Func<int,int,int> m_evaluateDelegate;

private Operator(string sSymbol, int iPrecedenceLevel, Func<int,int,int> evaluateDelegate):this(sSymbol, iPrecedenceLevel)
m_evaluateDelegate = evaluateDelegate;

public int Evaluate(int iValue1, int iValue2)
return m_evaluateDelegate(iValue1,iValue2);

Green. Ditto for the other operators -, *, /
All done. Finally a console app to do this

static void Main(string[] args)
ExpressionConverter expr = new ExpressionConverter();

Console.WriteLine("Postfix version is ");
foreach (object term in expr.ConvertInfixToPostfix(args[0]))
{ Console.Write(term + " "); }

Console.WriteLine("Expression evaluated to " + expr.EvaluateInfixExpression(args[0]) );

This is how it works.
Release>DynCalc.exe "((1+2) + 3) * 2 - 8/4"
Postfix version is
1 2 + 3 + 2 * 8 4 / -
Expression evaluated to 10

Now ExpressionConverter is no longer a converter.. we should probably rename it to Expression. Also it has no instance state. All methods can therefore be converted to static methods - no need to create an instance to invoke members. Done.
Other than non-happy paths like malformed expressions.. (can be done) it's all good. End of series. I had fun..

No comments:

Post a Comment