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.

 

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.

Serializing and Deserializing JSON in C#

The majority of my systems integration work requires me to work with 3rd party API’s or to create my own APIs. When creating my own, obviously I have full control over what the API call needs to be sent and what it will return and what shape its in. Pretty much all of my APIs work with XML data, its nice and easy to work with and the majority of people understand it at a glance.

More recently I was passed a set of 3rd party APIs that work with JSON (JavaScript Object Notation). For the purposes of this post, I am assuming that you know what JSON is and are comfortable with it. If you want to read more on JSON, the following link will take you over to Wikipedia where you can read more – http://en.wikipedia.org/wiki/JSON.

A very simple JSON string looks as follows:

{"forename" : "Phil", "surname" : "Curnow", "age" : 41}

We have a simple set of Name/Value pairs. In order to work with this data, we certainly don’t want to start writing code to parse the name/value pairs, its just not worth it. Ideally we would like to return this data in an object. To do this we can deserialize the JSON string. The following code snippet will explain how to do this. In order for this code to work, ensure that you have the following using’s at the top of your code:

using System.Runtime.Serialization;
using System.Runtime.Serialization.Json;

The chances are, you will also need to add a reference to System.Runtime.Serialization in your Visual Studio project. With all of this done, you should now be able to work with the following code.

Creating a Person Class

As already mentioned, we want to deserialize the JSON string into an object. In order to do this, we obviously need to create a class, we will call this class Person. Pay particular attention to the attributes used within the class declaration and the properties.

[DataContract]
class Person
{
    [DataMember]
    public string forename { get; set; }
    [DataMember]
    public string surname { get; set; }
    [DataMember]
    public int age { get; set; }
}

You will see that our properties are named exactly the same as the name in the name/value pairs in the JSON string. We can then write the following code to deserialize the string.

string jsonString = @"{""forename"" : ""Phil"", ""surname"" : ""Curnow"", ""age"" : 41}";

DataContractJsonSerializer ser = new DataContractJsonSerializer(typeof(Person)); 
MemoryStream stream = new MemoryStream(Encoding.UTF8.GetBytes(jsonString)); 
Person obj = (Person)ser.ReadObject(stream);

Our deserialized string is now in the object obj (which is of the type Person). With this in mind, we can access the properties of the object by simply using obj.forename, obj.surname, etc. To make life a little easier, you could always set the object obj as follows:

var obj = (Person)ser.ReadObject(stream);

Working with an Array of JSON Objects

What do we do if we have more than one person defined in our JSON string, such as:

[{"forename" : "Phil", "surname" : "Curnow", "age" : 41},{"forename" : "Lorna", "surname" : "Curnow", "age" : 44}]

As it stands, our deserialization code will not work with this JSON string, we need a little tweaking. Basically, we need to return a list of People objects, so our code will now look as follows:

string jsonString = @"[{""forename"" : ""Phil"", ""surname"" : ""Curnow"", ""age"" : 41},{""forename"" : ""Lorna"", ""surname"" : ""Curnow"", ""age"" : 44}]";

DataContractJsonSerializer ser = new DataContractJsonSerializer(typeof(List<Person>)); 
MemoryStream stream = new MemoryStream(Encoding.UTF8.GetBytes(jsonString)); 
var obj = (List<Person>)ser.ReadObject(stream);

Notice that we have now specified List<Person> in our code. We can then use the following to display the person data to the console:

foreach (Person p in obj)
    Console.WriteLine("Forename: {0} - Surname: {1}", p.forename, p.surname);

Now this is all very well, but do we really want to write that same block of code each time we want to work with a different data type? Well, probably not!! and this is where a quick conversion of the code to a generic method comes in handy. By simply creating the following generic method, we now have a piece of code that should work with any data type:

public static T DeserializeJSon<T>(string jsonString) 
{
    DataContractJsonSerializer ser = new DataContractJsonSerializer(typeof(T));
    MemoryStream stream = new MemoryStream(Encoding.UTF8.GetBytes(jsonString));
    T obj = (T)ser.ReadObject(stream);
    return obj;
}

Rewriting the above deserialization now becomes as simple as this:

var obj = DeserializeJSon<Person>(jsonString);

or

var obj = DeserializeJSon<List<Person>>(jsonString);

A More Complex JSON String

Whilst I am not going to cover the multitude of different JSON strings you could work with, there is one more I want to show you. Consider the following string (formatted for easier reading):

{
    "forename":"Phil",
    "surname":"Curnow",
    "age":41,
    "address":
    {
        "line1":"21 High Street",
        "line2":"Anyplace, AnyTown, AN1 1AB"
    }
}

We now have an address included, which is made up of name/value pairs in its own right. So how do we deserialize this kind of string? Well, its actually very easy. All we have to do is create a new class for the address data and add a property of the type address to the Person class, as follows:

[DataContract]
class Address
{
    [DataMember]
    public string line1 { get; set; }
    [DataMember]
    public string line2 { get; set; }
}

Our Person class is then modified as follows:

[DataContract]
class Person
{
    [DataMember]
    public string forename { get; set; }
    [DataMember]
    public string surname { get; set; }
    [DataMember]
    public int age { get; set; }
    [DataMember]
    public Address address { get; set; }
}

The address is then handled correctly and the address lines placed in the address property.

Naming Class Properties Differently to JSON Names

You will more than likely want to name your class properties differently to their JSON counterparts. Consider the possibility of having the name/value pair current-account-balance:210.00. Personally I would not want a property in my class named current-account-balance!! To overcome this, we can slightly modify the [DataMember] attribute declaration to the following:

[DataMember (Name="current-account-balance")]
public decimal AccountBalance { get; set; }

This then defines a property in our class called AccountBalance that will contain the value of the current-account-balance.

Serializing Data to JSON

As you can guess, there is an opposite to deserializing, which is serializing. Consider the fact that we have created a Person object, or a list of Person objects and we want to convert this to a JSON string and return this from an API call. As with the deserialization, we need to write a generic method that will convert any type to its JSON equivalent. This method is as follows:

public static string SerializeJSon<T>(T t)
 {     
    MemoryStream stream = new MemoryStream();
    DataContractJsonSerializer ds = new DataContractJsonSerializer(typeof(T));
    DataContractJsonSerializerSettings s = new DataContractJsonSerializerSettings();
    ds.WriteObject(stream, t);
    string jsonString = Encoding.UTF8.GetString(stream.ToArray());
    stream.Close();
    return jsonString;
}

If we then create a Person object as follows:

Person p = new Person
{
    forename = "Phil",
    surname = "Curnow",
    age = 41,
    address = new Address { line1 = "21 High Street", line2 = "Anyplace, AnyTown, AN1 1AB" }
};

We can simply convert it to a JSON string using the method call:

string jsonString = SerializeJSon<Person>(p);

Or with a list of Person objects, as follows:

List<Person> people = new List<Person>();
people.Add(new Person ...  );
people.Add(new Person ... );

string jsonString = SerializeJSon<List<Person>>(people);

Conclusion

As you can see, working with JSON data in C# is not at all difficult with the facilities built into the .NET Framework. If you are planning to work with JSON data to a larger extent, it is worth spending time investigating JSON further to become comfortable with looking at the data and being able to model it using classes.