Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / desktop / Win32

Yet Another Convertor From Infix To Postfix Expressions!

4.83/5 (8 votes)
4 Nov 2014CPOL 13.3K  
A very powerful and customizable source code that converts the Infix to Postfix expression.

Introduction

I know that there are a lot of source codes for converting Infix expression to Postfix expression in any programming languages. But often in some of these source codes, you may see that the Operands, Operators and the Operator's Values are always specific. For example, the Operands are always digits or numeric and the Operators are always (+, -, *, /) and the rule of Operator's values is that the value of (*) and (/) are always greater than (+) and (-) and so on...

But in this source code, you can define your own Operands, Operators and Operator's Values!

Output of Code

Using the Code

C#
using System.Linq;

namespace MyConsoleApplication
{
    /// <summary>
    /// This Program Was Written By Mr. Dariush Tasdighi
    /// .NET Framework 4.5 - C# Language - Console Application
    /// www.IranianExperts.com
    /// Version 1.0.1
    /// </summary>
    public class Program
    {
        static void Main(string[] args)
        {
            System.Collections.Generic.List<Utility.Operator> oOperators =
                new System.Collections.Generic.List<Utility.Operator>();

            oOperators.Add(new Utility.Operator("+", 1));
            oOperators.Add(new Utility.Operator("-", 1));
            oOperators.Add(new Utility.Operator("*", 2));
            oOperators.Add(new Utility.Operator("/", 2));

            string strInput = string.Empty;

            // Sample (1)
            strInput =
                "( a + b ) + c * d - f";

            var varOutput =
                Utility.ConvertInfixToPostFix(strInput, oOperators);

            System.Console.WriteLine();
            foreach (var varItem in varOutput)
            {
                System.Console.Write(varItem + " ");
            }
            // /Sample (1)

            // Sample (2)
            strInput =
                "( A + B ) * D + E / ( F + A * D )";

            varOutput =
                Utility.ConvertInfixToPostFix(strInput, oOperators);

            System.Console.WriteLine();
            foreach (var varItem in varOutput)
            {
                System.Console.Write(varItem + " ");
            }
            // /Sample (2)

            // Sample (3)
            strInput =
                "( ( A + B * C ) + D * E ) - F / G * H";

            varOutput =
                Utility.ConvertInfixToPostFix(strInput, oOperators);

            System.Console.WriteLine();
            foreach (var varItem in varOutput)
            {
                System.Console.Write(varItem + " ");
            }
            // /Sample (3)

            System.Console.Write("\n\r\n\rPress [Enter] To Exit...");
            System.Console.ReadLine();
        }
    }

    public static class Utility
    {
        public class Operator : System.Object
        {
            public Operator(string name, int value)
            {
                Name = name;
                Value = value;
            }

            public int Value { get; set; }
            public string Name { get; set; }
        }

        static Utility()
        {
        }

        private static bool IsNodeOperator
            (string node, System.Collections.Generic.List<Operator> Operators)
        {
            var varNode =
                Operators
                .Where(current => string.Compare(current.Name, node, ignoreCase: true) == 0)
                .FirstOrDefault();

            if (varNode == null)
            {
                return (false);
            }
            else
            {
                return (true);
            }
        }

        private static bool IsOperatorValueOfLeftIsGreaterThanRight
            (string left, string right, System.Collections.Generic.List<Operator> Operators)
        {
            if ((right == "(") || (right == ")"))
            {
                return (true);
            }
            else
            {
                Operator oLeftOperator =
                    Operators
                    .Where(current => string.Compare(current.Name, left, ignoreCase: true) == 0)
                    .FirstOrDefault();

                Operator oRightOperator =
                    Operators
                    .Where(current => string.Compare(current.Name, right, ignoreCase: true) == 0)
                    .FirstOrDefault();

                if (oLeftOperator.Value > oRightOperator.Value)
                {
                    return (true);
                }
                else
                {
                    return (false);
                }
            }
        }

        public static System.Collections.Generic.List<string> ConvertInfixToPostFix
            (string input, System.Collections.Generic.List<Operator> Operators)
        {
            if (string.IsNullOrWhiteSpace(input))
            {
                return (null);
            }

            input = input.Trim();

            while (input.Contains("  "))
            {
                input = input.Replace("  ", " ");
            }

            string[] strNodes = input.Split(' ');

            System.Collections.Generic.List<string> oOutput =
                new System.Collections.Generic.List<string>();

            System.Collections.Generic.Stack<string> oOpreratorsStack =
                new System.Collections.Generic.Stack<string>();

            foreach (string strNode in strNodes)
            {
                if ((strNode != "(") &&
                    (strNode != ")") &&
                    (IsNodeOperator(strNode, Operators) == false))
                {
                    oOutput.Add(strNode);
                }
                else
                {
                    if (strNode == "(")
                    {
                        oOpreratorsStack.Push(strNode);
                    }
                    else
                    {
                        if (strNode == ")")
                        {
                            if (oOpreratorsStack.Count == 0)
                            {
                                throw (new System.Exception("Unexpected Error!"));
                            }

                            string strLastStackItem =
                                oOpreratorsStack.Pop();

                            while (strLastStackItem != "(")
                            {
                                oOutput.Add(strLastStackItem);

                                if (oOpreratorsStack.Count == 0)
                                {
                                    break;
                                }

                                strLastStackItem =
                                    oOpreratorsStack.Pop();
                            }
                        }
                        else
                        {
                            if (oOpreratorsStack.Count == 0)
                            {
                                oOpreratorsStack.Push(strNode);
                            }
                            else
                            {
                                string strPeek =
                                    oOpreratorsStack.Peek();

                                while (IsOperatorValueOfLeftIsGreaterThanRight
                                    (strNode, strPeek, Operators) == false)
                                {
                                    string strLastStackItem =
                                        oOpreratorsStack.Pop();

                                    oOutput.Add(strLastStackItem);

                                    if (oOpreratorsStack.Count == 0)
                                    {
                                        break;
                                    }

                                    strPeek = oOpreratorsStack.Peek();
                                }

                                oOpreratorsStack.Push(strNode);
                            }
                        }
                    }
                }
            }

            while (oOpreratorsStack.Count > 0)
            {
                string strLastStackItem =
                    oOpreratorsStack.Pop();

                oOutput.Add(strLastStackItem);
            }

            return (oOutput);
        }
    }
}

Points of Interest

This source code is useful for some people that want to write some special interpreters for Accounting Systems or for those who want to participate in some International Software Exams, etc.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)