Building Expression Evaluator with Expression Trees in C# – Part 2

Introduction

In my previous post, I showed how to build a simple expression evaluator using expression trees. Although it works fine it has some drawbacks:

• It does not support parentheses.
• It does not support variables.
• In some cases the result can be wrong as the parser is not using left to right parsing.
• It is compiling delegates for every expression which results in slower execution.

To solve these issues we will use a different algorithm and deal with all points except variable support.

Implementing expression evaluator using Shunting yard algorithm

The algorithm that we are going to implement is called Shunting yard algorithm and works like this:

1. If the next token is number add it to operand stack.
2. If it is an operation token and operator stack is empty push it to operator stack.
3. If it is an operation token and operator stack is not empty and current operation has higher precedence push it to operator stack. If not pop the operator from stack and evaluate it with arguments from the operand stack and jump to step 2.
4. When we reach the end evaluate all operations on the stack.

Translating this into code is pretty straightforward and results in the following expression evaluator:

public decimal Evaluate(string expression)
{
    if (string.IsNullOrWhiteSpace(expression))
    {
        return 0;
    }

    var expressionStack = new Stack<Expression>();
    var operatorStack = new Stack<char>();

    using (var reader = new StringReader(expression))
    {
        int peek;
        while ((peek = reader.Peek()) > -1)
        {
            var next = (char)peek;

            if (char.IsDigit(next))
            {
                expressionStack.Push(ReadOperand(reader));
                continue;
            }

            if (Operation.IsDefined(next))
            {
                var currentOperation = ReadOperation(reader);

                while (true)
                {
                    if (operatorStack.Count == 0)
                    {
                        operatorStack.Push(next);
                        break;
                    }

                    var lastOperition = operatorStack.Peek();

                    if (currentOperation.Precedence > ((Operation)lastOperition).Precedence)
                    {
                        operatorStack.Push(next);
                        break;
                    }

                    var right = expressionStack.Pop();
                    var left = expressionStack.Pop();

                    expressionStack.Push(((Operation)operatorStack.Pop()).Apply(left, right));
                }
                continue;
            }

            if (next != ' ')
            {
                throw new ArgumentException("Invalid character encountered", "expression");
            }
        }
    }

    while (operatorStack.Count > 0)
    {
        var right = expressionStack.Pop();
        var left = expressionStack.Pop();

        expressionStack.Push(((Operation)operatorStack.Pop()).Apply(left, right));
    }

    var compiled = Expression.Lambda<Func<decimal>>(expressionStack.Pop()).Compile();
    return compiled();
}

internal sealed class Operation
{
    private readonly int precedence;
    private readonly string name;
    private readonly Func<Expression, Expression, Expression> operation;

    public static readonly Operation Addition = new Operation(1, Expression.Add, "Addition");
    public static readonly Operation Subtraction = 
           new Operation(1, Expression.Subtract, "Subtraction");
    public static readonly Operation Multiplication = 
           new Operation(2, Expression.Multiply, "Multiplication");
    public static readonly Operation Division = 
           new Operation(2, Expression.Divide, "Division");

    private static readonly Dictionary<char, Operation> 
                   Operations = new Dictionary<char, Operation>
    {
        { '+', Addition },
        { '-', Subtraction },
        { '*', Multiplication},
        { '/', Division }
    };

    private Operation(int precedence, Func<Expression, Expression, 
                      Expression> operation, string name)
    {
        this.precedence = precedence;
        this.operation = operation;
        this.name = name;
    }

    public int Precedence
    {
        get { return precedence; }
    }

    public static explicit operator Operation(char operation)
    {
        Operation result;

        if (Operations.TryGetValue(operation, out result))
        {
            return result;
        }
        else
        {
            throw new InvalidCastException();
        }
    }

    public Expression Apply(Expression left, Expression right)
    {
        return operation(left, right);
    }

    public static bool IsDefined(char operation)
    {
        return Operations.ContainsKey(operation);
    }
}

This code passes all the tests we have in previous post and solves issues three and four. Let’s refactor it and extract common code in a separate method:

private void EvaluateWhile(Func<bool> condition)
{
    while (condition())
    {
        var right = expressionStack.Pop();
        var left = expressionStack.Pop();

        expressionStack.Push(((Operation)operatorStack.Pop()).Apply(left, right));
    }
}

The evaluate method now looks like this:

public decimal Evaluate(string expression)
{
    if (string.IsNullOrWhiteSpace(expression))
    {
        return 0;
    }

    operatorStack.Clear();
    expressionStack.Clear();

    using (var reader = new StringReader(expression))
    {
        int peek;
        while ((peek = reader.Peek()) > -1)
        {
            var next = (char)peek;

            if (char.IsDigit(next))
            {
                expressionStack.Push(ReadOperand(reader));
                continue;
            }

            if (Operation.IsDefined(next))
            {
                var currentOperation = ReadOperation(reader);

                EvaluateWhile(() => operatorStack.Count > 0 &&
                              currentOperation.Precedence <= ((Operation)operatorStack.Peek()).Precedence);

                operatorStack.Push(next);
                continue;
            }

            if (next != ' ')
            {
                throw new ArgumentException(string.Format(
                  "Encountered invalid character {0}", next), "expression");
            }
        }
    }

    EvaluateWhile(() => operatorStack.Count > 0);

    var compiled = Expression.Lambda<Func<decimal>>(expressionStack.Pop()).Compile();
    return compiled();
}

At this point we are ready to add support for parentheses. Our goal is to make the following test pass:

[Test]
public void Supports_Parentheses()
{
    Assert.That(engine.Evaluate("2*(5+3)"), Is.EqualTo(2 * (5 + 3)));
    Assert.That(engine.Evaluate("(5+3)*2"), Is.EqualTo((5 + 3) * 2));
    Assert.That(engine.Evaluate("(5+3)*5-2"), Is.EqualTo((5 + 3) * 5 - 2));
    Assert.That(engine.Evaluate("(5+3)*(5-2)"), Is.EqualTo((5 + 3) * (5 - 2)));
    Assert.That(engine.Evaluate("((5+3)*3-(8-2)/2)/2"), Is.EqualTo(((5 + 3) * 3 - (8 - 2) / 2) / 2m));
    Assert.That(engine.Evaluate("(4*(3+5)-4-8/2-(6-4)/2)*((2+4)*4-(8-5)/3)-5"),
                Is.EqualTo((4 * (3 + 5) - 4 - 8 / 2 - (6 - 4) / 2) * ((2 + 4) * 4 - (8 - 5) / 3) - 5));
    Assert.That(engine.Evaluate("(((9-6/2)*2-4)/2-6-1)/(2+24/(2+4))"),
                Is.EqualTo((((9 - 6 / 2) * 2 - 4) / 2m - 6 - 1) / (2 + 24 / (2 + 4))));
}

We only need to add the following changes:

• If the token is left parentheses push it to operator stack.
• If the token is right parentheses evaluate all operators in operator stack until we reach left parentheses.

The first point is really straightforward and for the second one we can use the EvaluateWhile method we introduced above. After adding this code our method looks like this:

public decimal Evaluate(string expression)
{
    if (string.IsNullOrWhiteSpace(expression))
    {
        return 0;
    }

    operatorStack.Clear();
    expressionStack.Clear();

    using (var reader = new StringReader(expression))
    {
        int peek;
        while ((peek = reader.Peek()) > -1)
        {
            var next = (char)peek;

            if (char.IsDigit(next))
            {
                expressionStack.Push(ReadOperand(reader));
                continue;
            }

            if (Operation.IsDefined(next))
            {
                var currentOperation = ReadOperation(reader);

                EvaluateWhile(() => operatorStack.Count > 0 && operatorStack.Peek() != '(' &&
                                    currentOperation.Precedence <= ((Operation)operatorStack.Peek()).Precedence);

                operatorStack.Push(next);
                continue;
            }

            if (next == '(')
            {
                reader.Read();
                operatorStack.Push('(');
                continue;
            }

            if (next == ')')
            {
                reader.Read();
                EvaluateWhile(() => operatorStack.Count > 0 && operatorStack.Peek() != '(');
                operatorStack.Pop();
                continue;
            }

            if (next != ' ')
            {
                throw new ArgumentException(
                  string.Format("Encountered invalid character {0}", next), 
                  "expression");
            }
        }
    }

    EvaluateWhile(() => operatorStack.Count > 0);

    var compiled = Expression.Lambda<Func<decimal>>(expressionStack.Pop()).Compile();
    return compiled();
}

Conclusion

Modifying our expression evaluator using shunting yard algorithm was pretty easy and has several advantages compared to previous implementation. In the next post, we will add support for parsing expressions with variables.