Click here to Skip to main content
Click here to Skip to main content

Tagged as

Converting InFix to PostFix using C#

, 21 Apr 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
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:

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:

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:

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:

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)

Share

About the Author

mariazingzing

United States United States
No Biography provided

Comments and Discussions

 
QuestionJust another version of Infix to Postfix Conversion Pinmemberxtreme performer27-Feb-13 3:45 
BugBug in IsValid() method PinmemberMember 36586544-Dec-12 4:50 
QuestionThere is a lesson to learn: don't do it like this PinmemberAndreas Gieriet23-Apr-12 0:20 
QuestionWhats wrong with this black box test?????????? [modified] Pinmemberperilbrain22-Apr-12 1:12 
Enter InFix Expression: (((2+3+9)+89+0+8))
 
Not a valid Epression!
 
Enter InFix Expression: (((2+3+9)+89+0+8)-0)
 
Not a valid Epression!
 
Enter InFix Expression: (((2+3+9)+89+0+8)-0)-00
 
Not a valid Epression!
 
Enter InFix Expression: 1+2
 
PostFix: 12+
 
And this one was killing!!!
Enter InFix Expression: 0001+1234+(0098*00)
 
Not a valid Epression!
 
I am DEAD....
Enter InFix Expression: 1+1+1+1+1*0*0*0*0*0*0*0*0
 
Not a valid Epression! Cry | :((

modified 22-Apr-12 7:23am.

AnswerBecause: Pinmembermariazingzing22-Apr-12 9:58 
GeneralRe: Because: Pinmemberperilbrain22-Apr-12 19:53 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.141015.1 | Last Updated 21 Apr 2012
Article Copyright 2012 by mariazingzing
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid