Conversion of Expressions from Infix to Postfix Notation in C# – Part 3 Custom Functions

Conversion of Expressions from Infix to Postfix Notation in C# – Part 1

Conversion of Expressions from Infix to Postfix Notation in C# – Part 2 Unary Operators

Having taken a couple of days off work to catch up with a few things, I’ve now finally got some time available to post part 3 of the series on Infix to Postfix conversion, which shows how to implement custom functions into our expression parser. So here it is.

At the moment we have implemented an expression parser that works with mathematical operators and also handles negative numbers, but to make it a more complete solution, we should also be able to handle functions in our expressions. Quite a few of the examples I have seen ‘hard code’ a library of functions into the parser, which means you are limited to whats been provided or you need to modify the expression parser itself to handle any additional functions you require. With my solution, I want to make it as flexible as possible and allow additional functions to be added without having to modify any of the parser code and I think what I am going to present here goes some way to achieving this.

The Solution

My solution for adding custom functions is to allow the user to code the function as a class (e.g. Add, Sub, Sin, Cos) and ‘add’ this to the parser. In order to do this, we need to be able to set up a ‘function library’ within the parser and this can contain none or as many functions as you require. Adding a function later on should be a simple matter of coding the function class and then adding it to the function library. So how can we do this?

The IFunction Interface

The easiest way to achieve this is to have our function classes implement the IFunction interface. The interface looks as follows:

public interface IFunction
{
    int TotalParameters
    {
        get;
    }

    double[] Parameters
    {
        get;
        set;
    }

    double Execute();
}

The TotalParameters property has a getter and this will return how many parameters the function call is expecting. The Parameters property is an array and enables all of the parameters for the function to be passed. Finally, the Execute method will hold the code for the function. For a function that adds two numbers together, our Add class would look as follows:

public class Add : IFunction
{

    public int TotalParameters
    {
        get { return 2; }
    }

    public double[] Parameters
    {
        get;
        set;
    }

    public double Execute()
    {
        return Parameters[0] + Parameters[1];
    }
}

As our Add function expects two parameters, TotalParameters is set to return the value 2. The Execute method takes the two parameters passed via the Parameters property and simple returns the two numbers added together, very easy.

The Function Library

The grandly named function library is nothing more than the following:

private static Dictionary<string, IFunction> functions = new Dictionary<string, IFunction>();

This is simply a dictionary where the string is the name of the function (e.g. Add, Sub) and an instance of our function class. To add a function to the library, we use the AddFunction method:

//add a new user defined function to the function library
public static void AddFunction(string functionName, IFunction functionInstance)
{
    functions.Add(functionName, functionInstance);
}

So adding our Add function to the library is as simple as:

Evaluate.AddFunction("Add", new Add());

Now we can create our functions and add them to the parser, how do we add the functionality to the parser to know what to do with them?

Extending the Parser

There are two parts of the parser to extend, the InfixToPostfix method (conversion of our expression to Postfix) and the CalculateExpression method.

We first need to make a change to the GetPrecedence method. Originally this simply used the table of operators to return the precedence value for the operator, but we now need to take into account functions. We are going to give functions a higher precedence than any of the operators, now we could simply do this by looking at the highest precedence number in the operator table and return that number+1, but if we add more operators to the parser, we need to make sure that we also modify the precedence method, not ideal. The method has been modified to find the highest precedence value in the operator table and return n+1 if what is passed in is a function, here we can see the modification:

private static int GetPrecedence(string s)
{
           
    int max = 0;
    //if the passed is a function, make it the highest precedence
    //we simply get the max precedence value for all maths operators and add 1
            
    if(functions.ContainsKey(s))
        max = Math.Max(operators[operators.Keys.First()][0],
                       operators[operators.Keys.Last()][0])+1;
    else
        max= operators[s][0];

    return max;
}

This method now looks after itself if more operators are added.

We now need to modify the loop that iterates over the component parts of the Infix expression and converts to Postfix, so what do we need to do? I will break this down into a series of steps for handling functions. To fully understand this, I would urge you to read the Wikipedia article on the Shunting Yard Algorithm.

Step 1

Within the loop we check if the token we are currently looking at is a function (e.g. Add, Sub), if it is, we simply push this onto our stack and do nothing more with it.

 Step 2

We now need to handle argument separators (i.e. commas) in the parameter list for the function. The Shunting Yard algorithm says that: Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.  Remember that we are handling opening parenthesis already in the conversion, so opening parenthesis for a function are already handled. We handle the separators using a simple loop, as follows:

else if (s==",")
{
    while (stack.Peek() != "(")
        queue.Enqueue(stack.Pop());
}

This is all we have to do to modify the Infix to Postfix conversion method. We now need to make a modification to the CalculateExpression method as we actually do want to be able to do something meaningful with it. Again, the modification is not at all difficult and the new piece of code in the method is as follows:

//if we have a function, check it exists and execute with required parameters
else if (functions.ContainsKey(token))
{
    IFunction func = functions[token];

    //we now need to pop off the required amount of parameters
    double[] paramList = new double[func.TotalParameters];
    for (int i = 0; i < paramList.Length; i++)
        paramList[i] = stack.Pop();

    //reverse the parameter array as they are popped off in reverse order
    Array.Reverse(paramList);
    func.Parameters = paramList;
    stack.Push(func.Execute());
}

In the same way we check for the differing operators we support when calculating the expression, we need to see if the token we are currently pointing to is a function, if it is, we then call the function with the required parameters. The code above is working as follows:

1. func will contain the instance of the function we wish to call. func is of the type IFunction and this is fine, as our function classes must implement the IFunction interface.
2. By looking at the TotalParameters property for the function (instance pointed to by func), we know how many parameters we must obtain from the stack and pass to our function. We store these in the paramList array.
3. As the parameters have been popped off the stack in the reverse order, we need to reverse the array before setting the Parameters property for the function class.
4. Finally, we execute the function by calling the Execute method and push the result onto the stack.

Thats all there is to it, not too difficult at all.

Time to Test!

Now, lets test some expressions containing some functions and see what we get:

Using the expression Add(1,2)=1+2 we can check that our function returns 3. If we run this through the evaluator it should return 1, meaning true:

Lets try Add(1,2)+Add(3,4), which should return 10:

We can then rewrite the expression above using nothing but functions, that is Add(Add(1,2),Add(3,4)):

And finally, lets add another function into the expression. Sub(Add(Add(1,2),Add(3,4)),5). We are taking our original expression which gave us 10 and then subtracting 5 from it using the Sub function, which should obviously gives us a result of 5.

As you can see, all of our expressions evaluated correctly so it looks like we have working function support in our parser.

One point to note is the fact that functions are case sensitive, if you define a function called Add and then refer to it in your expression as ADD or add, it will not be found, you must use Add.

This post now ends the mini series on Infix to Postfix conversion and evaluation. I hope you find the code useful. Judging by the emails I have received from readers, you have found the code useful so far. I have left it to the reader to add any exception handling if you make use of the code.

As with the previous posts, I have uploaded the Visual Studio 2013 solution containing the code, which can be found here.

• Custom Functions
• Functions
• Infix
• Infix to Postfix Conversion
• Postfix
• Reverse Polish Notation
• RPN