Infix To Prefix Conversion using Stack C Program

By | October 5, 2016

Learn how to convert an expression from Infix to Prefix using Stack in C Programming. This code for infix to prefix in c uses two arrays to store infix and prefix expression and a stack for conversion from infix to prefix expression.

Infix To Prefix Conversion Example

Infix String: X+Y/Z-M*N+O

Prefix String: +-+X/YZ*MNO

C Program For Infix To Prefix Conversion using Stack

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int pop();
int precedence(char symbol);
int isEmpty();
void infix_to_prefix();
int checker(char symbol);
void push(long int symbol);

char prefix_string[20], infix_string[20], postfix_string[20];
int top;
long int stack[20];

int main()
{
      int count, length;
      char temp;
      top = -1;
      printf("\nEnter an Expression in Infix format:\t");
      scanf("%[^\n]s", infix_string);
      infix_to_prefix();
      printf("\nExpression in Postfix Format: \t%s\n", postfix_string);
      length = strlen(postfix_string) - 1;
      strncpy(prefix_string, postfix_string, 20);
      for(count = 0; count < length; count++, length--)
      {
            temp = prefix_string[count];
            prefix_string[count] = prefix_string[length];
            prefix_string[length] = temp;
      }
      printf("\nExpression in Prefix Format: \t%s\n", prefix_string);
      return 0;
}

void infix_to_prefix()
{
      unsigned int count, temp = 0;
      char next;
      char symbol;	
      for(count = 0; count < strlen(infix_string); count++)
      {
            symbol = infix_string[count];
            if(!checker(symbol))
            {
                  switch(symbol)
                  {
                        case '(': push(symbol);
                                  break;
                        case ')':
                                  while((next = pop()) != '(')
                                  {
                                        postfix_string[temp++] = next;
                                  }
                                  break;
                        case '+':
                        case '-':
                        case '*':
                        case '/':
                        case '%':
                        case '^':
                                  while(!isEmpty() && precedence(stack[top]) >= precedence(symbol))
                                  postfix_string[temp++] = pop();
                                  push(symbol);
                                  break;
                                  default: 
                                           postfix_string[temp++] = symbol;
                  }
            }
      }
      while(!isEmpty()) 
      {
            postfix_string[temp++] = pop();
      }
      postfix_string[temp] = '\0';
}

int precedence(char symbol)
{
      switch(symbol)
      {
            case '(': return 0;
            case '+':
            case '-':
                      return 1;
            case '*':
            case '/':
            case '%':
                      return 2;
            case '^':
                      return 3;
            default:
                      return 0;
      }
}

int checker(char symbol)
{
      if(symbol == '\t' || symbol == ' ')
      {
            return 1;
      }
      else
      {
            return 0;
      }
}

void push(long int symbol)
{
      if(top > 20)
      {
            printf("Stack Overflow\n");
            exit(1);
      }
      top = top + 1;
      stack[top] = symbol;
}

int isEmpty()
{
      if(top == -1)
      {
            return 1;
      }
      else
      {
            return 0;
      }
}

int pop()
{
      if(isEmpty())
      {
            printf("Stack is Empty\n");
            exit(1);
      }
      return(stack[top--]);
}

Output

C Program To Convert Infix To Prefix Expression using Stack

In case you get any compilation errors or any doubts in this C Program For Conversion of Infix Expression to Prefix Expression, let us know about it in the Comment Section below.

Recommended Programs
C Program For Counting Sort Algorithm
C Program For Depth First Search Algorithm using Recursion
C Program To Evaluate a Prefix Expression using Stack
C Program For Prefix To Infix Expression Conversion
C Program For Postfix To Prefix Expression Conversion
C Program To Evaluate a Postfix Expression using Stack
C Program For Infix To Postfix Expression Conversion
C Program For Postfix To Infix Expression Conversion
C Program For Linear Search Algorithm
C Program To Implement Singly Linked List using Arrays

4 thoughts on “Infix To Prefix Conversion using Stack C Program

  1. Rehan Bala

    This is funny. I searched for infix to prefix conversion everywhere. Didnt get any working program. But, your program works. Thanks!

    Reply
  2. Parag Shah

    Prefix means operators before the operand and infix means operators within the operands, right?

    Reply

Let's Discuss