Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C#
Tip/Trick

Converting InFix to PostFix using C#

Rate me:
Please Sign up or sign in to vote.
4.36/5 (9 votes)
21 Apr 2012CPOL 72.7K   8   8
How to convert infix to postfix using c# in simple expressions. But the base is not defferent for complicated expressions.

Introduction

Most of compilers use PostFix to generat native code. For more information about PostFix, refer here.

I want to talk about a simple code in C# to preception it.

Using the code

The program is under Console. The operands have to be one digit numbers in this program. Here the main code:

C#
static void Main(string[] args)
{
   string inFix, postFix = string.Empty;
   while (true)
   {
      Console.Write("Enter InFix Expression: ");
      inFix = Console.ReadLine().Replace(" ", string.Empty);
      if (IsValid(inFix))//Validates InFix Expression
      {
         Console.WriteLine("\nPostFix: {0}",ConvertToPostFix(inFix));
         break;
      }
   Console.WriteLine("\nNot a valid Epression!\n");
   }
   Console.ReadKey();
}

All right, I used some methods and wanted to declare them.

Declaring ConvertToPostFix:

C#
private static string ConvertToPostFix(string inFix)
{
   StringBuilder postFix = new StringBuilder();
   char arrival;
   Stack<char> oprerator = new Stack<char>();//Creates a new Stack
   foreach (char c in inFix.ToCharArray())//Iterates characters in inFix
   {
      if (Char.IsNumber(c))
         postFix.Append(c);
      else if (c == '(')
         oprerator.Push(c);
      else if (c == ')')//Removes all previous elements from Stack and puts them in 
                        //front of PostFix.  
      {
         arrival = oprerator.Pop();
         while (arrival != '(')
         {
            postFix.Append(arrival);
            arrival = oprerator.Pop();
         }
      }
      else
      {
         if (oprerator.Count != 0 && Predecessor(oprerator.Peek(), c))//If find an operator
         {
            arrival = oprerator.Pop();
            while (Predecessor(arrival, c))
            {
               postFix.Append(arrival);

               if (oprerator.Count == 0)
                  break;

               arrival = oprerator.Pop();
            }
            oprerator.Push(c);
         }
         else
            oprerator.Push(c);//If Stack is empty or the operator has precedence 
      }
   }
   while (oprerator.Count > 0)
   {
      arrival = oprerator.Pop();
      postFix.Append(arrival);
   }
   return postFix.ToString();
}

In this code if user enters 12+3-55+c, it will raise error for 12 and c. Because it's a simple program and compares characters one by one. They sould be numeric. The best input is an expression like this: (9*(1-3))-4*(3+3*4) and the result will be: 913-*4334*+*-

Comparing the precedences:

C#
private static bool Predecessor(char firstOperator, char secondOperator)
{
   string opString = "(+-*/%";

   int firstPoint, secondPoint;

   int[] precedence = { 0, 12, 12, 13, 13, 13 };// "(" has less prececence

   firstPoint = opString.IndexOf(firstOperator);
   secondPoint = opString.IndexOf(secondOperator);

   return (precedence[firstPoint] >= precedence[secondPoint]) ? true : false;
}

Clear!

Validation Mehod:

C#
Private static bool IsValid(string input)
{
   Regex operators = new Regex(@"[\-+*/%]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
   if (string.IsNullOrEmpty(input))
      return false;

   if (input.ToCharArray().Select(c => c == '(').Count() != input.ToCharArray().Select(c => c == ')').Count())
      return false;

   string tempString = operators.Replace(input, ".");

   if (tempString.EndsWith("."))
      return false;

   string[] contains = new string[] { "(.)", "()", "..", ".)" };

   foreach (string s in contains)
   {
      if (tempString.Contains(s))
         return false;
   }

   operators = new Regex(@"[().]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
   tempString = operators.Replace(tempString, string.Empty);

   foreach (char c in tempString.ToCharArray())
   {
      if (!Char.IsNumber(c))
         return false;
   }

   if (input.Contains("."))
      return false;

   tempString = input;

   operators = new Regex(@"[1234567890]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
   tempString = operators.Replace(tempString, ".");

   if (tempString.Contains(".."))
      return false;
   if (input.StartsWith("*") || input.StartsWith("/") || input.StartsWith("%") 
                                             || input.StartsWith("+") || input.StartsWith("-"))
      return false;

   contains = new string[] {"(%","(/","(*","*","(+","(-" };
   foreach (string s in contains)
   {
      if (input.Contains(s))
         return false;
   }

   int begin = 0, end = 0;
   foreach (char c in input)
   {
      if (c == '(')
         begin++;
      if (c == ')')
         end++;
      if (end > begin)
         return false;
}
return true;
} 

(Thanks to OriginalGriff for some advising)

Validation method, unlike its harash exterior, works easy.

It checks all parenthesis:

  • Number of "(" and ")" if doesn't match, returns false.
  • If for example: ((1+3)))(, return's false
  • if "*1" or "/5" or "%9" or ...
  • if "(+" or "(-" or ...
  • ...

And for all invalid expression, returns false.

License

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


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
Questiontakes every input as invalid expression Pin
yash shekhada18-Jan-16 18:01
yash shekhada18-Jan-16 18:01 
QuestionBug in ConvertToPostFix() method Pin
keerthini26-Oct-15 12:14
keerthini26-Oct-15 12:14 
QuestionJust another version of Infix to Postfix Conversion Pin
xtreme performer27-Feb-13 3:45
xtreme performer27-Feb-13 3:45 
BugBug in IsValid() method Pin
Member 36586544-Dec-12 4:50
Member 36586544-Dec-12 4:50 
QuestionThere is a lesson to learn: don't do it like this Pin
Andreas Gieriet23-Apr-12 0:20
professionalAndreas Gieriet23-Apr-12 0:20 
QuestionWhats wrong with this black box test?????????? Pin
perilbrain22-Apr-12 1:12
perilbrain22-Apr-12 1:12 
AnswerBecause: Pin
mariazingzing22-Apr-12 9:58
mariazingzing22-Apr-12 9:58 
GeneralRe: Because: Pin
perilbrain22-Apr-12 19:53
perilbrain22-Apr-12 19:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.