From Infix to Postfix – an alternative to shunting yard

When I was 19 years old I wanted to create a command line interface in gwbasic! I though long and hard about how I would parse a command line and then interprete it. A friend told me I should convert the command to postfix. “2 + 3″ is called infix. Postfix for that would be “2 3 +”. The good thing about it is that postfix is very easy to interprete. Every time you find an argument, such as 2 and 3 in the example, you push it to a stack. When you get to an operator, such as +, you pop the two required arguments from the stack, perform the addition and push the 5 back to the stack.

Dealing with precedence is also very easy. I found a way of doing this, that I think may be original. I would just push every operator to the right following a simple rule. After tokenizing the input string I start with the leftmost token. I walk that token to the right as long as it has lower precedence and as long as it passes the same number of (‘s and )’s. After I walk the first token, I walk the second. That’s all there is to it!

This is not the same way Dijkstra does it with the shunting yard algorithm which uses a stack. All I need is an array! I have tried it with lot’s of different scenarios. I treat operands the same as operators.

This is actually the first time I have ever thought of publishing it. I started thinking someone might take an interest in it. So here it is.

The code example here is a complete example with a rudimentary tokenizer. To try it, compile it with C# 3.5 or port it to your preferred procedural language. After compilation run it with spaces between all tokens. Like PostFix.exe 2 * ( 2 + 3 )

using System;
using System.Collections.Generic;

namespace PostFix
{
    class Program
    {
        static void Main(string[] args)
        {
            Token[] tokens;

            if (args.Length == 0)
            {
                Console.WriteLine("You called this program without arguments,\nplease enter something for me to calculate.\nPlease remember to use spaces between numbers and operators\nas I am just a sample program without complicated parsing code.");
                string input=Console.ReadLine();
                tokens = Tokenize(input.Split(new char[] { ' ' }));
            }
            else
                tokens = Tokenize(args);

            PostFix(tokens);

            float result = Execute(tokens);

            Console.WriteLine("Result is: {0}\nPress enter to exit.",result);

            Console.ReadLine();
        }

        private static void PostFix(Token[] tokens)
        {
            for (int i = 0; i < tokens.Length - 1; i++)             {                 if (tokens[i].Precedence > tokens[i + 1].Precedence)
                {
                    int j = i;
                    int scopes = 0;
                    while (j < tokens.Length - 1 && (scopes > 0 ||
                        tokens[j].Precedence > tokens[j + 1].Precedence))
                    {
                        Token tmp = tokens[j];
                        tokens[j] = tokens[j + 1];
                        tokens[j + 1] = tmp;
                        scopes += ((tokens[j].Operator == '(') ? 1 : 0)
                            - ((tokens[j].Operator == ')') ? 1 : 0);
                        j++;
                    }
                    i--;
                }
            }
        }

        private static float Execute(Token[] tokens)
        {
            Stack stack = new Stack();
            foreach (Token token in tokens)
            {
                switch (token.Operator)
                {
                    case '+':
                        stack.Push(stack.Pop() + stack.Pop());
                        break;
                    case '-':
                        {
                            float f1 = stack.Pop();
                            float f2 = stack.Pop();
                            stack.Push(f2 - f1);
                        }
                        break;
                    case '*':
                        stack.Push(stack.Pop() * stack.Pop());
                        break;
                    case '/':
                        {
                            float f1 = stack.Pop();
                            float f2 = stack.Pop();
                            stack.Push(f2 / f1);
                        }
                        break;
                    case '(':
                    case ')':
                        break;
                    default:
                        stack.Push(token.Operand);
                        break;
                }
            }
            float result = stack.Pop();
            return result;
        }

        private static Token[] Tokenize(string[] args)
        {
            Token[] tokens = new Token[args.Length];
            int i = 0;
            foreach (string arg in args)
            {
                Token token = new Token();
                switch (arg)
                {
                    case "+":
                    case "-":
                        token.Operator = arg[0];
                        token.Precedence = 2;
                        break;
                    case "*":
                    case "/":
                        token.Operator = arg[0];
                        token.Precedence = 1;
                        break;
                    case "(":
                        token.Operator = arg[0];
                        token.Precedence = -1;
                        break;
                    case ")":
                        token.Operator = arg[0];
                        token.Precedence = 3;
                        break;
                    default:
                        if (!float.TryParse(arg, out token.Operand))
                            throw new ArgumentException("Unknown token: " + arg);
                        token.Precedence = 0;
                        break;
                }
                tokens[i++] = token;
            }
            return tokens;
        }
    }

    public struct Token
    {
        public char Operator;
        public float Operand;
        public int Precedence;

        public override string ToString()
        {
            if (Operator != 0)
                return Operator.ToString();
            else
                return Operand.ToString();
        }
    }
}