C Program To Convert Infix Expression To Prefix Expression

Advertisements
Advertisements

 236 total views

In this article, we discuss about writing a C program to convert infix expression to prefix expression. The infix expression is of form operand operator operand and it is converted to operator operand operand form.

Consider the following example.

// Infix expression
((A + B) * C)

// Prefix expression
*+ABC

Problem Definition

The user enters an infix expression and the C program converts the infix expression to prefix equivalent expression.

The program uses a character array to receive the input expression and another character array to output the final prefix expression. The program use a stack S to keep track of operators and parenthesis of the expression.

Advertisements

Here is the algorithm to convert infix expression to prefix expression.

  1. Scan the infix expression right to left.
  2. If the character is right parenthesis “)”, push to stack S.
  3. If the character is left parenthesis “(“, then start popping stack one by one and put the characters into prefix array.
  4. If the scanned character is operator , compare with the operator on stack and continuously pop operators from stack if scanned operator has less precedence than the operator on the top of the stack. If scanned operator has higher precedence than top of the stack. Put the operator on the stack.
  5. If scanned character is an operand, directly put it in the prefix array.
  6. If all scanned character is finished , start popping stack and put the operators in prefix array one by one.

For example, suppose we want to convert the infix expression ((A + B) * C) into prefix expression.

Step 1: Start scanning from right to left of the infix expression.

Step 2: Identify the character and put it in stack or prefix array accordingly.

Scanned character  Type          Stack     Prefix array   Stack Operation
--------------------------------------------------------------------------
)                    operator      )                           push(')')
C                    operand                    C                  n/a
*                    operator      *                           push('*')
)                    operator      )                           push(')')
B                    operand                    B                  n/a
+                    operator      +                           push('+')
A                    operator                   A                  n/a
(                    operator                   +              pop()
                                                *              pop()
(                    operator      (                           pop()

Prefix Array :-  *+ABC

Functions Used In the Program

The program uses functions to perform scan, pop from stack, push to stack, check the precedence of operators, etc. Each of these function is discussed in the following sections.

Stack Functions

void push(char sym)
{
   top = top + 1;
   s[top] = sym;
}
char pop ()
{
  char item;
  item = s[top];
  top = top-1;
  return item;
}

Identify priority of scanned character

You need to identify the priority level of scanned character so that we can compare it with the operator on the top of the stack . The function will return a number for each scanned character.

int G (char symbol)
{
  switch (symbol)
  {
    case '+':
    case '-': return 2;
    case '*': 
    case '/': return 4;
    case '^': 
    case '$': return 5;
    case '(': return 0;
    case ')': return 9;
    default : return 7;
  }

}

Identify priority of character on the top of the stack

This function will return the priority of a character on the top of the stack. We must compare it with the priority of the scanned character. If scanned character has higher priority , push it into the stack.

Else start popping characters from stack and push them into prefix array until scanned character priority become higher.

int F (char symbol)
{
  switch (symbol)
  {
    case '+':
    case '-': return 1;
    case '*': 
    case '/': return 3;
    case '^': 
    case '$': return 6;
    case '(': return 0;
    case '#': return -1;
    default : return 8;
  }

}

Infix expression to prefix expression converter

Advertisements

This the main function that does character by character scan of infix expression. Let’s look at the variable declarations.

/* Global Declarations */
int pos = 0;
int top;      /* top of the stack pointer */
int length;   /* length of the expression */
char symbol;  /* scanned character */
char temp;    /* when item is popped from stack we will keep it in temp */
char s[30];   /* stack of type character */
char infix;   /* infix expression */
char prefix;  /* prefix array for prefix expression */
/* 
void infix_prefix (char infix[], char prefix[])
{
  int i, t1;
  top = -1;               /* stack is empty */
  length = strlen(infix); /* length of infix expression */
  length = length - 1;    /* The length of the expression 
  pos = length;             is used for prefix array 
  t1 = length;              and infix array */

/* start scanning the infix expression */
while ( length >= 0)
{
   symbol = infix[length];
   switch(symbol)
   {  
      /* if ) push to stack */
      case ')': push(symbol); 
                break; 
      /* if ( start popping from 
      stack unless a matching ) 
      not found */
      case '(': 
                temp = pop();
                while( temp != ')')
                {  
                     prefix[pos] = temp;
                     pos--;
                     temp = pop();
                }
                if (temp != ')')
                {
                   prefix[pos--] = pop();
                }
                   break;
     case '+':
     case '-':
     case '*':
     case '$':
     case '/':
     case '^': while(F(s[top]) >= G(symbol)) /* if priority of stack is more than
               {                                scanned symbol, then keep 
                                                popping stack until priority 
                                                of stack top become less than 
                                                the scanned character */
                 temp = pop();
                 prefix[pos] = temp;
                 pos--;
               }
                 push(symbol);
                 break;
     default: 
                 prefix[pos--] = symbol;
                 break;
   }
    length--;                                /*after scanning each character
                                               decrement length to the 
                                               next character */
    {
          while(s[] != '#')                 /* when all characters are 
                                               scanned, then start popping
          {                                    stack and put every thing
             temp = pop();                     prefix array */
             prefix[pos--] = temp;
          }
    for (i = 0; i < t1; i++)                /* reverse the expression in prefix 
    {                                          array to get the correct result */
         prefix[i] = prefix[i + pos + 1];
    }

Flowchart – infix to prefix

Flowchart - Infix expression to prefix expression conversion
Flowchart – Infix expression to prefix expression conversion

Program Code – Infix To Prefix

#include <stdio.h>
#include <string.h>
#include <conio.h>

/* Global Declarations */
int pos = 0;
int top;      
int length;   
char symbol;  
char temp;   
char s[30];   
char infix;   
char prefix;  

void push(char sym)
{
   top = top + 1;
   s[top] = sym;
}

char pop ()
{
  char item;
  item = s[top];
  top = top-1;
  return item;
}

int G (char symbol)
{
  switch (symbol)
  {
    case '+':
    case '-': return 2;
    case '*': 
    case '/': return 4;
    case '^': 
    case '$': return 5;
    case '(': return 0;
    case ')': return 9;
    default : return 7;
  }

}
int F (char symbol)
{
  switch (symbol)
  {
    case '+':
    case '-': return 1;
    case '*': 
    case '/': return 3;
    case '^': 
    case '$': return 6;
    case '(': return 0;
    case '#': return -1;
    default : return 8;
  }

}

void infix_prefix (char infix[], char prefix[])
{
  int i, t1;
  top = -1;               
  length = strlen(infix); expression */
  length = length - 1;   
  pos = length;             
  t1 = length;              


while ( length >= 0)
{
   symbol = infix[length];
   switch(symbol)
   {  
      
      case ')': push(symbol); 
                break; 
      
      case '(': 
                temp = pop();
                while( temp != ')')
                {  
                     prefix[pos] = temp;
                     pos--;
                     temp = pop();
                }
                if (temp != ')')
                {
                   prefix[pos--] = pop();
                }
                   break;
     case '+':
     case '-':
     case '*':
     case '$':
     case '/':
     case '^': while(F(s[top]) >= G(symbol))
               {                                
                 temp = pop();
                 prefix[pos] = temp;
                 pos--;
               }
                 push(symbol);
                 break;
     default: 
                 prefix[pos--] = symbol;
                 break;
   }
    length--;                                
    {
          while(s[] != '#')                 
          {                                    
             temp = pop();                     
             prefix[pos--] = temp;
          }
    for (i = 0; i < t1; i++)             
    {                           
         prefix[i] = prefix[i + pos + 1];
    }
/* MAIN PROGRAM */
void main ()
{
 clrscr();
 printf("Enter the valid infix expression\n');
 scanf("%s",infix);
 infix_prefix(infix, prefix);
 printf("The prefix expression \n");
 printf("%s\n",prefix);
 getch();
}

Output

*+ABC
Advertisements
Advertisements
Advertisements