SSIS 2014 Package Downgrade

Recently I had a need to be able to take an SSIS package created using SSIS for SQL Server 2014 and add the package to a preexisting SSIS 2012 solution. By default, it is not possible to take the package and add it to the existing 2012 solution as the package format is not backwards compatible.

After a fairly quick Google search, I came across a blog post by Vanie Castro who explained what he manually did to an SSIS 2014 package to ‘downgrade’ it to SSIS 2012. His detailed post can be found here. Following these instructions, I was able to successfully take my 2014 package and downgrade it and add it to my SSIS 2012 solution.

There was still some further adjustment to do to the package once it was in the 2012 solution, but it was certainly loadable. The manual changes were mainly around Script tasks, but this was easily fixed.

The Downgrade Tool

If you have several packages that require downgrading, performing this manually can be a time consuming process. Using the instructions on Vanie’s blog post, I created a simple downgrade tool which enables 1 or more packages to be converted automatically.

SSIS 2014 Downgrade
The downgrade process mainly revolves around replacing Component ID’s and Element Types. The downgrade tool is provided with two XML mapping files that contain the ComponentID and ElementType mappings. The mappings look to be fairly complete, but if any are missing, these files can be edited to add any missing mappings. If you do find any missing mappings, could you let me know and I will add them to the XML files in the package distribution.

The tool has been uploaded to CodePlex where the source code to the latest version can be found. If you would  rather download the an executable version without the source code, this can be found here. Full instructions on how to use the tool can be found on the Codeplex site.

If you find the downgrade tool useful or have any comments or questions about it, feel free to email me or leave a comment on this post and I will reply as soon as I can.

 

MVVMBlocks .NET MVVM Framework

mvvmblocksI have decided to release my MVVM framework for Windows Store Applications. MVVMBlocks is a very easy to use framework for implementing the MVVM pattern in your applications.

I have been using the framework successfully for quite a while in my applications and it performs well. I have put a full page together to explain how to implement the framework in your applications along with some example Visual Studio 2013 solutions.

MVVMBlocks is available as a NuGet package and can be installed from there from within Visual Studio. The NuGet page for MVVMBlocks can be found here. I’m planning on releasing the source code to the framework, so you can see how each of the MVVM framework elements have been implemented. This will also enable you to make any changes you see fit to the framework. As soon as I have released the code, I will post an entry with details to where you can download/view the code.

I would be really pleased to hear from you if you decide to use the framework. If you make any code changes, I would be more than happy to hear about these and potentially implement your changes in future versions of the framework.

 

Creating a Windows 10 Preview Virtual Machine with VMWare Player

Having a long weekend enables me to get things done that I otherwise wouldn’t have time for. One of the things I’ve wanted to do for a while is create a Virtual Machine with Windows 10 on it, so I can use Windows 10 and also start looking at application development for it. I’m glad to say that I’ve now had the time to create the virtual machine and it went fine. I thought I would write this post to detail the steps I took to create the VM.

You will need to download the Windows 10 Insider Preview ISO which can be found here – You will need to be signed up to the Windows Insider Programme before you can download, but that’s not a lengthy process at all.

Creating the Virtual

I have used VMWare Player Version 7.1.0 build-2496824 to build the Virtual Machine. Follow the steps below and you should end up with a working Windows 10 virtual.

Step 1 – Create New Virtual Machine

From the VMWare Player menu, select Create New Virtual Machine. You will then see a dialog box similar to the one below.

New VM
Browse to the location where you saved the ISO file and select it. Then click on Next >. Type in the name you would like to give to the VM and select the location where the VM files will be stored. This should look similar to the settings below.

New VM 2

Again, click Next > to go to the next page of the wizard. This next page allows you to further customise the VM settings. The most I did here was change the amount of RAM given to the VM. I’d recommend giving the VM as much as you can. Obviously, don’t give the VM the same as you have in the host machine.

New VM 3

Click on Finish and the VM should start to be created.

Hyper-V Issues

When I first tried to create the VM, I received a VMWare and Hyper-V compatibility error as shown below.

HyperV Error

This is easy enough to overcome, just do the following:

  1. Open  Hyper-V Manager and select stop service
  2. Run a command prompt as an administrator and issue the command bcdedit /set hypervisorlaunchtype off
  3. Reboot and create the virtual again

To enable Hyper-V simply issue the command bcdedit /set hypervisorlaunchtype auto at the command prompt, again run this as administrator.

When the Windows 10 install starts, you should see similar to the following in VMWare Player.

Windows 10 Installing

For me, the install took around 35 to 40 minutes with a couple of reboots. Once the install is done, make sure you install VMWare Tools in the same way as you would for any other Windows VM.

Installed and Running!

You should now have Windows 10 happily installed and running. I’m even writing this post using the VM and the Spartan Browser!

Windows 10 Running

I quite like what I have seen so far. If you have come from Windows 8.1 you should have no problems finding your way around. I think for people who have never used Windows 8.1 it will be a bit of a shock to the system, but maybe not as much as Windows 8 and to a lesser extent 8.1 would have been.

My plan now is to install Visual Studio 2015 and start looking at application development, this really has been my main motivation for creating the virtual.

As you can see, creating a Windows 10 virtual is pretty much the same as any other, the only little gotcha I had was Hyper-V, but this was easily solved. As I start to get into Windows 10 and application development, I’ll blog further about how I am getting on.

I hope you find this post useful, and if you create yourself a virtual I’d really like to hear what you think of Windows 10.

 

 

Spend £2.50 or buy a new Computer

Bettery

Replacing this £2.50 battery saved buying a new Computer

My Mum and Dad have a couple of computers at home, a laptop that my Mum uses for email and browsing and a desktop computer my Dad uses for word processing. Not long ago the laptop did have to be replaced, after 7 years of use it had decided enough was enough and just refused to power on. For the cost of a new laptop it was better to replace it and they got a much higher spec machine which they are happy with.

Whilst working from home, I had a call on the Friday morning from them saying that the desktop machine wouldn’t power on, well the power supply fired into life, but “the blue light on the power button isn’t lighting up”. I couldn’t really comment on what the problem was at the time, as there wasn’t enough information to go on and I didn’t just want to say “it sounds like its had it, time to buy a new one”. To be honest, the machine is about 4 years old and if it had been used constantly it could well have decided enough was enough too and it was time for a replacement, but its not a heavily used machine, so I wasn’t convinced.

Saturday morning arrives and I go around and have a look at the machine. My mum had looked up the cost of a new machine and thought that a £300 machine would be alright for them to buy. The spec looked pretty good and would have been more than enough for their needs. I told them not to be to hasty on going out to buy a new one, lets see what can be done with this one first.

On firing up the machine, things did kick into life, power supply whirring away and the processor fan spinning away, but as they said, no blue light on the power button. I was surprised on how little dust was in the machine after 4 years, mine is a dust hog and requires a good clean every now and then.

In a previous couple of jobs, part of my role (apart from being a programmer!) was to sort out faulty PCs. Having been a consultant for the last 8 years I don’t get the chance to do this much any more. Time to see if I can get it working. Here are the things I looked at.

  1. All cables seated properly on the motherboard? – Yes!
  2. Any power going to the drives in the machine? – Yes! the Hard Drive did spin up
  3. Anything showing on the monitor? – Sort of! it briefly has a signal then loses it.
  4. Failing the POST (Power On Self Test)? – I don’t think its even getting that far!
  5. Remove the RAM and switch on, has the machine beeped away complaining? – No. I wanted to see at this point if it was doing the POST.
  6. Put RAM back in and take out CMOS battery, did it fire into life? – Oh yes! The “blue light” shone brightly and the machine booted, complaining that it had lost its settings. A quick press of F2 to use the defaults and away it went.

Happy with that I went off for a cup of tea and told Mum and Dad it was time to spend some money, not the £300 they were preparing themselves for, but a couple of pounds on a new battery. A quick trip to B&Q and £2.50 spent, the battery was put into the machine and all is well with it. I think they were surprised that something so simple could cause all those problems, until I explained why it was there and what it was doing.

It just goes to show that with a little playing around and running through a mental check-list of things to try, its worth spending the time trying to fix what appears to be broken. 20 minutes spent with my hands inside the machine saved them £297.50, now that’s got to be a good 20 minutes spent!

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:

Eval1

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

Eval2

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

Eval3

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.

Eval4

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.

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

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

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

Originally in the second part, I was going to add the ability to both evaluate expressions with the unary + and – and also build in support for functions. Due to time pressures I am going to have to save the addition of functions for part 3, but this will be added! Part 2 is going to concentrate on building in support for unary + and -.

What are Unary Operators

For an in-depth explanation you can read the Wikipedia article on this. You can see from the article that there are more unary operations than + and -, but these are the operators we are going to concentrate on supporting in our expression evaluator. Quite simply put, the expression -5 expresses negative 5. The expression 2 * -5 = -10. There is the concept of a unary +, so you could have the expression 2 * +5 = 10, but actually the unary + is not needed, because the 5 is assumed to be positive.

Why Explicitly Support This in Code

So why are we having to explicitly build in support for this in our parser? If you look back at Part 1, the Shunting Yard algorithm for converting infix to postfix is explained. As it stands, the unary operators are going to confuse the code that converts the expression. If you consider the infix expression 2 * 5, this converts to a postfix expression of 25* and using our code to evaluate this causes no problems at all. If you add in the unary – our (2 * -5) our code converts this to a postfix expression of 2*5- and when we try to evaluate this, our code is going to get very confused, so we need to do something to the code that converts the expression from infix to postfix to stop the confusion.

So what can we do? I have read a couple of articles to see how people have got around this. The first piece of good news and really this is obvious, we can ignore the unary + as it serves no real purpose. We first need to think about how we decide if an operator is a unary operator and there are a some simple rules we can follow, these are:

  1. If the + or – is the first character in the infix expression, its assumed to be unary. E.g. -5 * 2
  2. If the + or – comes after another operator, its assumed to be unary. E.g. 5 * -2
  3. If the + or – comes after an opening parenthesis, its assumed to be unary. E.g. 1 + (-5  * 2)

So that’s our rules, what can we do in code. Well a lot of responses on forums have said to find out if the operator is unary and if its a + ignore it and if its a – replace it with another character such as # or ~. That’s fine and would overcome the issue, but we then need to really play around with our code, both the infix to postfix converter and evaluation code and I want to avoid this if possible as the code seems to work well, is there an alternative? Well, yes I think there is, lets see how we can convert a positive number to a negative using simple maths. To convert 5 to -5 I would normally say ‘multiply by -1’, 5 * -1 = -5, but that doesn’t help us as there is a unary – in the expression and that’s what we are trying to replace!! So we could always do 0 – 5 = -5, that gives us -5 quite nicely and if you think about our expression, gives us a clue as to what we can do. Lets look at our three rules above, could we not do the following and derive the same answers?

  1. -5 * 2 = (0 – 5) *2
  2. 5 * -2 = 5 * (0 – 2)
  3. 1 + (-5 * 2) = 1 + ( (0 – 5) * 2 )

So our solution would involve a slight code change, which would be to applied to our infix expression before it is converted to postfix.

  1. Look for a unary +, if its found, remove it from the infix expression as its not needed.
  2. Look for a unary -, if its found, insert a ( and a 0 before the unary – and a ) after the operand the unary minus applies to.

We would then have a valid infix expression with the unary operators removed but produces the same result when evaluated, but more importantly, we have an infix expression that still works with our postfix conversion code.

The Code!

Enough theory, lets put this into code! We’ve said that we need to do the above before the expression is converted to postfix, so we are either going to build the code into our InfixToPostfix method, or write a method to work on the expression but call it from the InfixToPostfix method. I’m going to follow the route of writing a method and call it.

One of the first things our InfixToPostfix method does is to split an infix expression and produce a list of the expressions component parts, this makes adding and removing items from the expression nice and easy. Our original InfixToPostfix method had a LINQ expression that took our infix expression as a string, applied a regular expression to it and looped around the list. As I want to pass the expression converted to a list into our new method, I have refactored the method slightly to now do the following:

string pattern = @"(?<=[-+*/(),^<>=&])(?=.)|(?<=.)(?=[-+*/(),^<>=&])";
      
expression = expression.Replace(" ", "");
Regex regExPattern = new Regex(pattern);
List<string> expr = new List<string>(regExPattern.Split(expression));
expr.RemoveAll(s => String.IsNullOrEmpty(s.Trim()));
       
//parse our expression and fix unary + and -
ParseUnary(ref expr);
        
expr.ForEach(s =>

I’ve highlighted in bold our call to a method called ParseUnary which applies our rules we have derived above. This is a very simple method and looks as follows:

private static void ParseUnary(ref List<string> expr)
{
    for(int i = 0; i < expr.Count; i++)
    {
        //we have a minus
        //if its a unary, then the following happens:
        //1. At the beginning: -1 * 2 = ( 0 - 1 ) * 2
        //2. After an opening parenthesis: 1 + ( -2 * 3 ) = 1 + ( ( 0 - 2 ) * 3 )
        //3. After an operator: 1 + -2 = 1 + ( 0 - 2 )
        if (expr[i] == "-")
        {
            //is it at the beginning of the expression OR
            //it follows and opening parenthesis OR operator>
            //if so, its a unary minus
            if (i == 0 || expr[i - 1] == "(" || operators.ContainsKey(expr[i - 1]))
            {
                expr.Insert(i, "(");
                expr.Insert(i + 1, "0");
                expr.Insert(i + 4, ")");
            }
        }
        //we have a +
        else if(expr[i]=="+")
        {
            //is it at the beginning of the expression
            //OR it follows an opening parenthesis OR operator?
            //if so, we can drop it, as it serves no purpose
            if (i == 0 || expr[i - 1] == "(" || operators.ContainsKey(expr[i - 1]))
                expr.RemoveAt(i);
        }
    }
}

As you can see, we iterate over the list and apply our rules for checking if a + or a – is a unary operator. As we have said + can be ignored, so if we find one, we simply remove it from the list. If we find a unary -, we insert our leading ( and 0 before the unary – and then insert our closing parenthesis after the operand the unary – applied to. As we are passing the list that contains the expression by reference, we don’t need to return anything from our ParseUnary method. This style is personal choice.

And that’s it! We’ve added the new method and made the changes to the existing method to implement handling the unary + and -, so lets see this working with the expression 1 + (-5 * 2). This should give us the answer -9. Evaluate -5 * 2 first to give us -10 and then add 1 to it gives us -9.

Unary Expression Output
As you can see from the postfix expression in the image above, the (0-5) as been applied and when evaluated, has given us the correct answer of -9.

I have made available a new version of the Visual Studio solution that implements the new additions above and you can download this from here.

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

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

If you have a need in your applications to evaluate mathematical expressions and you search the term ‘convert infix to postfix’, you will find a huge amount of information and code out there that will get you to where you need to be, some with explanations of how the code is working, others with just the program code. This post will hopefully fulfill both criteria, by giving an explanation of what the code is doing and also provide the Visual Studio Solution (VS2013) I have produced.

This is all out there already, why do this?

Good question!! Over the past 12 months I have been pretty much working solidly on my day job (the one that pays the bills!) and haven’t been able to spend much of my spare time sitting back and writing code for pleasure. With all the travel I have had, the time spent at home has been with the family. I’ve found myself with 2 weeks off over the Christmas period and this has been an ideal time to spend some time coding for pleasure. I’ve got a tonne of code I could be writing for work, but I’ve needed to switch off from that totally (not easy!!). For some reason the idea of writing some code to do expression evaluation popped into my head and this was an ideal little coding project that I could dip in and out of over the couple of weeks off.

What do the conversion from Infix to Postfix?

If you are reading this post, you more than likely already know the difference between infix and postfix notation. For a good description of these two notations (and for that matter prefix), follow the link here, its a very good brief description of the three notations.

With infix expressions, writing an evaluator can be a fairly complicated task, you need to cater for parenthesized expressions (potentially levels deep) and this can become potentially complicated to code (recursion anyone?). For example, with the expression ( (A * B) + (C / D) ) your evaluator will need to take into account all the parenthesized parts in order to derive the correct answer. Throw into the mix that you may also want to use functions, e.g. sin, cos, and it suddenly becomes not so much fun to write.

Postfix (Reverse Polish Notation)

Postfix notation specifies that all operators follow all of their operands and all parenthesis are removed. Looking at our infix expression ( (A * B) + (C / D) ) its posfix form would be AB*CD/+. To write code to evaluate this becomes an awful lot easier. If our code utilises a stack, we can do the following:

infix: ( ( 5 * 5) + (4 / 2) )
postfix expression:  55*42/+

for each char in postfix expression
{
    if char is operator
    {
        rhs = Pop();
        lhs = Pop();
        switch(char)
        {
            case '*':
                Push(lhs*rhs);
                break;
            case '/':
                Push(lhs/rhs);
                break;
            ... all other operators ...
        }
    }
    else
        Push(char); //push non-operator value to the stack.
}

So, working this through using our pseudo-code above, we get the following:

  1. push 5 to the stack
  2. push 5 to the stack
  3. Char * is an operator, so pop values from the stack into lhs and rhs and evaluate 5 * 5 and push result 25 to the stack
  4. Push 4 to the stack
  5. Push 2 to the stack
  6. Char / is an operator, so pop values from the stack into lhs and rhs and evaluate 4 / 2 and push result 2 to the stack
  7. Char + is an operator, so pop values from the stack into lhs and rhs and evaluate 25 + 2 and push result 27 to the stack
  8. END as postfix expression has been evaluated

Converting from Infix Please!!

Having read everything above, it all looks wonderful, but how to we get from infix to postfix and is it difficult? Fortunately this is not a difficult process and there is an algorithm for this called the Shunting Yard Algorithm. This is the algorithm we are going to implement. My code does not support functions or unary + and -. In part 2 of this series I will implement support for functions and unary + and -.

I’m not going to put the Shunting Yard Algorithm in this post, as I have linked to it above, so we can dive into the code that performs the conversion.

Operator Precedence and Associativity

The algorithm needs to take into account operator precedence and associativity when it constructs the postfix version of the expression. The wikipedia article gives this in the form of a table and this is what we will replicate in our code. We will implement this as a generic dictionary Dictionary<string,int[]) where the string will be the operator symbol and the integer array will hold the precedence and a value of 1 or 0 for either left or right association. The definition for this is as follows:

private static Dictionary<string, int[]> operators = new Dictionary<string, int[]>();
                 
//populate operators
//int format is {precedence, association -> 0=Left 1=Right}
operators.Add("^", new int[] { 5, 1 });
operators.Add("*", new int[] { 4, 0 });
operators.Add("/", new int[] { 4, 0 });
operators.Add("+", new int[] { 3, 0 });
operators.Add("-", new int[] { 3, 0 });
operators.Add("<", new int[] { 2, 0 });
operators.Add(">", new int[] { 2, 0 });
operators.Add("=", new int[] { 2, 0 });
operators.Add("&", new int[] { 1, 0 });

Our implementation of the algorithm also takes into account the operators < > = and &, so the precedence values have been modified compared to the Wikipedia article. Should you wish to add more operators you must make sure you get the precedence of the operator dictionary absolutely correct.

Starting the Conversion

 We then need to split our infix expression into its component parts so that we can parse it more easily. I’m using a regular expression to do this, as follows:

string pattern = @"(?<=[-+*/(),^<>=&])(?=.)|(?<=.)(?=[-+*/(),^<>=&])";
expression = expression.Replace(" ", "");
Regex regExPattern = new Regex(pattern);
    
regExPattern.Split(expression).Where(s => !String.IsNullOrEmpty(s.Trim())).ToList().ForEach(s =>
{

I don’t profess to be an expert with regular expressions and there is a small side effect with our expression in that it does produce empty elements in our list when we perform the split. This I think is to do with grouping within the regex and I will address this, but for the time being, I’m removing these in the LINQ expression when I start to iterate over the elements of the expression.

Compared to the algorithm explanation, I’m handling the order I do things slightly differently. I’m first checking if the element of the infix expression is an operator, if so, we process it, if not we go on to handle opening and closing parenthesis. If the element is neither of these things, its an operand and I’m simply adding it to the output queue. The order I have done things is just personal choice, it just seemed more logical to me.

    //is our token one of our defined operators
    //deal with precedence and association
    if (operators.ContainsKey(s))
    {
        //while the stack is not empty and the top of the stack is not an (
        while (stack.Count > 0 && stack.Peek() != "(")
        {
            if ((GetAssociation(s) == 0 && GetPrecedence(s) <= 
                                           GetPrecedence(stack.Peek())) ||
                (GetAssociation(s) == 1 && GetPrecedence(s) < 
                                           GetPrecedence(stack.Peek()))
               )
                queue.Enqueue(stack.Pop());
            else
                break;
        }
      
        //push operator onto the stack
        stack.Push(s);
    }
           
    //handle opening parenthesis
    //simply push this on the stack
    else if (s == "(")
    {
        stack.Push(s);
    }
    //handle closing parenthesis
    //pop all operators off the stack until the matching 
    //opening parenthesis is found and then discard the
    //opening parenthesis
    else if (s == ")")
    {
        while (stack.Count != 0 && stack.Peek() != "(")
            queue.Enqueue(stack.Pop());
      
        //forget the (
        stack.Pop();
    }
    else
        //none of the above so queue it
        queue.Enqueue(s);
});
            
//pop off the rest of the stack
while (stack.Count != 0)
    queue.Enqueue(stack.Pop());

return queue;

When we enter the loop to process the expression elements, we are first checking if the element is a valid operator, if it is, we are checking to see if there are any operators on the stack. If there are, we perform the precedence and association check for our current operator against what is on the top of the stack and pop off the operator on the stack and add to the output queue if required, pushing our currently selected operator element onto the stack. If we don’t have any operators on the stack, we simply push our operator onto the stack.

If our current operator in the expression is an opening parenthesis, we simply push this onto the stack and that’s all.

If our currently operator in the expression is a closing parenthesis, we pop all operators off the stack and add them to the output queue up to the point of the matching opening parenthesis. We then pop off and forget about the opening parenthesis, in other words, we don’t add it to the output queue.

Finally if the element in our expression is neither an operator or an opening or closing parenthesis, we assume that its an operand and we add it to the output queue.

When all expression elements have been processed within the loop, we check to see if there any operators left on the stack, if there are, we simply pop them off the stack and add them to the output queue.

And that’s it!! We then just return the queue as a return parameter from the method. My decision to use a Queue within the method is just personal choice and may or may not be a good decision, quite probably a generic list would have been better.

There are a couple of additional methods used that obtain the precedence and association values and these are shown below.

//Get the precedence of the operator passed in
private static int GetPrecedence(string s)
{
    return operators[s][0];
}
     
//Get the association of the operator passed in
private static int GetAssociation(string s)
{
    return operators[s][1];
}

To use these methods, we simply pass in the operator and the associated precedence or association value is returned.

The Output

I have wrapped all my code into a class called Evaluate and with this in mind, the code I can use to convert an infix expression to postfix and display the result is:

string exp = "( (5 * 5) + (4 / 2) )";
    
Console.WriteLine("Infix Expression: {0}", exp);
    
Console.Write("Postfix Expression: ");
Queue<string> q = Evaluate.InfixToPostFix(exp);
    
foreach (string s in q)
    Console.Write(s);

The output on the console looks as follows:

Postfix Expression
Evaluating the Postfix Expression

So now we have the expression converted to postfix form, we need to evaluate it, after all this is the whole purpose of this post! At the beginning of this post, I gave the algorithm for evaluating a postfix expression, so there is no need to go over this again. The method to evaluate is as follows:

public static double CalculateExpression(Queue<String> postfix)
{
    Stack<double> stack = new Stack<double>();
    
    postfix.ToList<String>().ForEach(token =>
    {
        if (operators.ContainsKey(token))
        {
            if (stack.Count > 1)
            {
                double rhs = stack.Pop();
                double lhs = stack.Pop();
                switch (token)
                {
                    case "+":
                        stack.Push(lhs + rhs);
                        break;
                    case "-":
                        stack.Push(lhs - rhs);
                        break;
                    case "*":
                        stack.Push(lhs * rhs);
                        break;
                    case "/":
                        stack.Push(lhs / rhs);
                        break;
                    case "^":
                        stack.Push(Math.Pow(lhs, rhs));
                        break;
                    case "=":
                        stack.Push(Convert.ToDouble(lhs == rhs));
                        break;
                    case "<":
                        stack.Push(Convert.ToDouble(lhs < rhs));
                        break;
                    case ">":
                        stack.Push(Convert.ToDouble(lhs > rhs));
                        break;
                    case "&":
                        stack.Push(Convert.ToDouble((int)lhs & (int)rhs));
                        break;
                }
            }
        }
        else
            stack.Push(Convert.ToDouble(token));
    });

    //everything has been evaluated and our result is on the stack
    //so return it
    return stack.Pop();
}

To call this method, we simply pass in what was returned from our method that converts infix to postfix, for example:

string exp = "( (5 * 5) + (4 / 2) )";
    
Console.WriteLine("Infix Expression: {0}", exp);
Console.Write("Postfix Expression: ");
Queue<string> q = Evaluate.InfixToPostFix(exp);
               
foreach (string s in q)
    Console.Write(s);
    
Console.WriteLine("\nThe expression evaluates to: {0}", Evaluate.CalculateExpression(q));

The output on the console then looks as follows:

Postfix Expression Evaluation

As you can see, the expression is evaluated and returns the answer of 27, which in my book means the evaluation has worked!

Other Expression Types

As I have added the operators < > and & and = you can build and evaluation some more complex expressions, such as:

  • (2*2) = (1+3) which would return the value 1 meaning true
  • (2*2) < 1 which would return the value 0 meaning false

Conclusion

Whilst this has been a fairly long post, we have covered a lot of ground, both theory and program code. I hope you find this post useful and feel free to leave a comment or contact me via twitter (@pcurnow).

In part 2 of this series, we will look at adding the ability to evaluate functions and give the ability to add your own functions to be evaluated.

You can find a full Visual Studio 2013 solution that contains a full working version of the conversion and evaluation routines described in this post here.