Convert Array of Strings to PostFix Notation

The need to evaluate an expression at runtime is an old one and has been addressed many different ways. Today Gilles writes with links to many of the current tools or examples available on the web.

Gilles writes:

That’s a common question but not a so simple one! 🙂

In short you have to use a lexer and a parser, that’s the common way used by every compiler in the Univers.

It should be more simple to do with the next .net compiler (Roselyn).

Here a few shortcuts using this technique and one using dynamic programming:

http://www.codeproject.com/Articles/13779/The-expression-evaluator-revisited-Eval-function-i

http://www.blackbeltcoder.com/Articles/algorithms/a-c-expression-evaluator

https://flee.codeplex.com/

http://www.codeproject.com/Articles/18880/State-of-the-Art-Expression-Evaluation

http://ncalc.codeplex.com/

http://www.codeproject.com/Articles/18004/Net-Expression-Evaluator-using-DynamicMethod

I like working through the concept myself. Not because I can write a better tool. I do it so that I understand how different tools can work and to expand my understanding of how to solve software development problems.

At this point I would like to continue with how to use the output generated in yesterday’s example, and convert it into a postfix string. I’m not providing actual objects, but the technique used to handle the results. I’m taking into account that the user may override the order of operations by enclosing some portion of the formula in parentheses.

My process is not the most efficient. It may be simpler to understand than some of the other conversion methods I have seen on the net.

I’m going to start with the formula 10 + 20 – (40 * 2) / (20 * 2) + 4

The expected result would be:

40 * 2 = 80

20 * 2 = 40

80 / 40 = 2

10 + 20 – 2 + 4 = 32

If I used the rules presented yesterday I would start with an array of strings that look like

10 + 20 – ( 40 * 2 ) / ( 20 * 2 ) + 4

I need to translate that array into a postfix string that looks like

10 20 40 2 * 20 2 * / 4 + – +

Since this is in an array of strings I can use a for loop to process each individual component of the formula.

I start with an empty string for the new postfix expression. In C# we use a StringBuilder for performance.

I also start out with a stack of operations making it easier to handle order of precedence. To make handling parentheses easier, I use an array of stacks. I have a pointer to the current array item for a stack.

Each time I encounter a ( character, I create a new stack and add it to the array. I have a current stack pointer which is incremented so we are now processing operators on a new stack. Well talk about how this is used as we process each item.

Let’s start by evaluating each item one at a time

For each string in the array of formula items:

• If the item is a number write it immediately to the output
• If the string is An open parentheses “ (“
  • Create a new stack to store operators
  • Increment the current stack pointer
• If the string is a low precedence operation (+ -)
  • Push it onto the current stack
• If the string is a high precedence operation (* /)
  • If the current stack pointer > 0
    • Pop the current stack until the operator popped has an equal precedence or the end of the stack is reached
    • Push the current operation on the stack
    • Push back any lower precedence operators that were popped off the stack
  • Else
    • If the next string is a number
      • Write the next number to the output
      • Write the operator to the output
    • Otherwise
      • Pop the current stack until the operator popped has an equal precedence or the end of the stack is reached
      • Push the current operation on the stack
      • Push back any lower precedence operators that were popped off the stack
• If the string is a close parentheses “)”
  • Pop each items off the current operations stack and add it to the output
  • Decrement the stack pointer
  • Pop each high precedence operation off the now current stack and add to output

Now that you have processed each character in order the only thing left to do is add any operations remaining in the based parameter stack. Reaching the end of the string items is the same as finding a closing parentheses in the string list. The only difference is that here there is no closing parentheses to fire off this event in the original string represented by the operations in the first stack in your array of stacks.

• Pop all items off stacks[0] and add them to the output

Let’s look at the different object values as each character is processed:

You have now converted your formula into a postfix syntax.

I found a number of simpler examples on the net, but none of them handled parentheses accurately in my unit tests (or, I may not have implemented them correctly which is more likely the case  ).

I’ll bet you have a simpler technique. Why not share it here, or leave a link to your favorite technique in the comments below.

Cheers,

Ben