Infix to Prefix Conversion using Stack in C

Stacks

Converting Infix to Prefix Expression

As we know for the compiler it may be difficult to read an infix expression as it can’t start operations and assignments until it has read the whole expression and know about the precedence of various operations in the expression.

While prefix expression is easier for the compiler, as it is already sorted in accordance with precedence and compiler, can start assignments and operations, without caring about precedence.

Methods Discussed

Firstly we are going to discuss the manual way of calculating prefix. We will use this to understand the algorithm of the code.

Then we are going to code, the coding methods that we have used are –

  • Method 1 – Using Array
  • Method 2 – Dynamically created Stack

What are infix and prefix expressions?

  • Infix: Expressions of format (A + B) are called as infix expressions, these are just like mathematical expressions
    • Example – ((a / b) + c) - (d + (e * f ))
  • Prefix: Expressions wherein the operator comes before the operands are prefix expression like – Infix: (A + B) can be expressed as +AB
    • Example – Prefix result would be : -+/abc+d*ef
  • Postfix: Expression operator comes after the operands are prefix expression like – Infix: (A + B) can be expressed as AB+
    • Example – Prefix result would be: ab/c+def*+-

Steps to convert

  • Any infix op1 oper op2 can be written as op1 op2 oper
    • Where op1 = Operand 1
    • op2 = Operand2
    • oper = Operation
  • Example a + b can be written as ab+ in prefix

Problem (This is how to convert manually for MCQ Question in the exam)

  • Infix: (a / b + c) - ( d + e * f) can be written as ((a / b) + c) - ( d + (e * f))
  • Now, we have done the above according to associativity
  • Solving and converting innermost bracket to prefix
  • Step 1 –(/ab + c) - ( d + *ef)
  • Step 2 – Consider /ab and *ef as separate operand x and y
  • the innermost bracket now looks like (x + c) - (d + y)
    • Applying prefix it looks like – (+xc - +dy)replacing x and y here (+/abc - +d*ef)
  • Step 3 – Considering+/abc and+d*efas separate operand z and w, the final bracket looks like – (z - w)the result would be -zw
    • replacing z and w value = -+/abc+d*ef

Algorithm for Prefix

Given Infix - ((a/b)+c)-(d+(e*f))
  • Step 1: Reverse the infix string. Note that while reversing the string you must interchange left and right parentheses.
  • Step 2: Obtain the postfix expression of the infix expression Step 1.
  • Step 3: Reverse the postfix expression to get the prefix expression

This is how you convert manually for theory question in the exam

  1. String after reversal – ))f*e(+d(-)c+)b/a((
  2. String after interchanging right and left parenthesis – ((f*e)+d)-(c+(b/a))
  3. Apply postfix – Below is postfix (On this page you check infix to postfix conversion rule)
  4. Reverse Postfix Expression (Given After the table below)
Sr. no.ExpressionStackPrefix
0((( 
1(((( 
2f(((f
3*(((*f
4e(((*fe
5)((fe*
6+((+fe*
7d((+fe*d
8)(fe*d+
9(-fe*d+
10((-(fe*d+
11c(-(fe*d+c
12+(-(+fe*d+c
13((-(+(fe*d+c
14b(-(+(fe*d+cb
15/(-(+(/fe*d+cb
16a(-(+(/fe*d+cba
17)(-(+fe*d+cba/
18)(-fe*d+cba/+
19) fe*d+cba/+-
Final prefix: -+/abc+d*ef

Method 1 (Using Array)

Let us have a look at this method below –
Run
#include<stdio.h>
#include<string.h> 
#include<limits.h>
#include<stdlib.h>
# define MAX 100
int top = -1;
char stack[MAX];

// checking if stack is full
int isFull() {
    return top == MAX - 1;
} 

// checking is stack is empty
int isEmpty() { 
    return top == -1; 
}

// Push function here, inserts value in stack and increments stack top by 1
void push(char item) {
    if (isFull()) 
        return; 
	top++;
	stack[top] = item;
}

// Function to remove an item from stack.  It decreases top by 1 
int pop() { 
    if (isEmpty()) 
        return INT_MIN; 
        
    // decrements top and returns what has been popped      
    return stack[top--]; 
} 

// Function to return the top from stack without removing it 
int peek(){ 
    if (isEmpty()) 
        return INT_MIN; 
    return stack[top]; 
} 

// A utility function to check if the given character is operand 
int checkIfOperand(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); 
} 

// Fucntion to compare precedence
// If we return larger value means higher precedence 
int precedence(char ch) 
{ 
    switch (ch) 
    { 
    case '+': 
    case '-': 
        return 1; 

    case '*': 
    case '/': 
        return 2; 

    case '^': 
        return 3; 
    } 
    return -1; 
} 

// The driver function for infix to postfix conversion 
int getPostfix(char* expression) 
{ 
    int i, j;

    for (i = 0, j = -1; expression[i]; ++i) 
    { 
        // Here we are checking is the character we scanned is operand or not
        // and this adding to to output. 
        if (checkIfOperand(expression[i])) 
            expression[++j] = expression[i]; 

        // Here, if we scan character ‘(‘, we need push it to the stack. 
        else if (expression[i] == '(') 
            push(expression[i]); 

        // Here, if we scan character is an ‘)’, we need to pop and print from the stack  
        // do this until an ‘(‘ is encountered in the stack. 
        else if (expression[i] == ')') 
        { 
            while (!isEmpty(stack) && peek(stack) != '(') 
                expression[++j] = pop(stack); 
            if (!isEmpty(stack) && peek(stack) != '(') 
                return -1; // invalid expression              
            else
                pop(stack); 
        } 
        else // if an opertor
        { 
            while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack))) 
                expression[++j] = pop(stack); 
            push(expression[i]); 
        } 

    } 

    // Once all inital expression characters are traversed
    // adding all left elements from stack to exp
    while (!isEmpty(stack)) 
        expression[++j] = pop(stack); 

    expression[++j] = '\0'; 
    
}

void reverse(char *exp){

    int size = strlen(exp);
    int j = size, i=0;
    char temp[size];

    temp[j--]='\0';
    while(exp[i]!='\0')
    {
        temp[j] = exp[i];
        j--;
        i++;
    }
    strcpy(exp,temp);
}
void brackets(char* exp){
    int i = 0;
    while(exp[i]!='\0')
    {
        if(exp[i]=='(')
            exp[i]=')';
        else if(exp[i]==')')
            exp[i]='(';
        i++;
    }
}
void InfixtoPrefix(char *exp){

    int size = strlen(exp);

    // reverse string
    reverse(exp);
    //change brackets
    brackets(exp);
    //get postfix
    getPostfix(exp);
    // reverse string again
    reverse(exp);
}

int main()
{    
    printf("The infix is: ");

    char expression[] = "((a/b)+c)-(d+(e*f))"; 
    printf("%s\n",expression);
    InfixtoPrefix(expression); 

    printf("The prefix is: ");
    printf("%s\n",expression);

    return 0; 
}

Output

The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*ef

Method 2 (Dynamically created Stack)

Let us have a look on this method below –
Run
#include<string.h> 
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
# define MAX 100

// A structure to represent a stack 
struct Stack { 
    int top; 
    int maxSize;
    // we are storing string in integer array, this will not give error
    // as values will be stored in ASCII and returned in ASCII thus, returned as string again
    int* array; 
}; 

struct Stack* create(int max) 
{ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->maxSize = max; 
    stack->top = -1; 
    stack->array = (int*)malloc(stack->maxSize * sizeof(int));
    return stack; 
} 

// Checking with this function is stack is full or not
// Will return true is stack is full else false 
//Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ 
    if(stack->top == stack->maxSize - 1){
        printf("Will not be able to push maxSize reached\n");
    }
    // Since array starts from 0, and maxSize starts from 1
    return stack->top == stack->maxSize - 1; 
} 

// By definition the Stack is empty when top is equal to -1 
// Will return true if top is -1
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1; 
}

// Push function here, inserts value in stack and increments stack top by 1
void push(struct Stack* stack, char item) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = item; 
}

// Function to remove an item from stack.  It decreases top by 1 
int pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top--]; 
} 

// Function to return the top from stack without removing it 
int peek(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top]; 
} 

// A utility function to check if the given character is operand 
int checkIfOperand(char ch) 
{ 
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); 
} 

// Fucntion to compare precedence
// If we return larger value means higher precedence 
int precedence(char ch) 
{ 
    switch (ch) 
    { 
    case '+': 
    case '-': 
        return 1; 

    case '*': 
    case '/': 
        return 2; 

    case '^': 
        return 3; 
    } 
    return -1; 
} 

// The driver function for infix to postfix conversion 
int getPostfix(char* expression) 
{ 
    int i, j; 

    // Stack size should be equal to expression size for safety  
    struct Stack* stack = create(strlen(expression)); 
    if(!stack) // just checking is stack was created or not  
        return -1 ; 

    for (i = 0, j = -1; expression[i]; ++i) 
    { 
        // Here we are checking is the character we scanned is operand or not
        // and this adding to to output. 
        if (checkIfOperand(expression[i])) 
            expression[++j] = expression[i]; 

        // Here, if we scan character ‘(‘, we need push it to the stack. 
        else if (expression[i] == '(') 
            push(stack, expression[i]); 

        // Here, if we scan character is an ‘)’, we need to pop and print from the stack  
        // do this until an ‘(‘ is encountered in the stack. 
        else if (expression[i] == ')') 
        { 
            while (!isEmpty(stack) && peek(stack) != '(') 
                expression[++j] = pop(stack); 
            if (!isEmpty(stack) && peek(stack) != '(') 
                return -1; // invalid expression              
            else
                pop(stack); 
        } 
        else // if an opertor
        { 
            while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack))) 
                expression[++j] = pop(stack); 
            push(stack, expression[i]); 
        } 

    } 

    // Once all inital expression characters are traversed
    // adding all left elements from stack to exp
    while (!isEmpty(stack)) 
        expression[++j] = pop(stack); 

    expression[++j] = '\0'; 
    
}

void reverse(char *exp){

    int size = strlen(exp);
    int j = size, i=0;
    char temp[size];

    temp[j--]='\0';
    while(exp[i]!='\0')
    {
        temp[j] = exp[i];
        j--;
        i++;
    }
    strcpy(exp,temp);
}
void brackets(char* exp){
    int i = 0;
    while(exp[i]!='\0')
    {
        if(exp[i]=='(')
            exp[i]=')';
        else if(exp[i]==')')
            exp[i]='(';
        i++;
    }
}
void InfixtoPrefix(char *exp){

    int size = strlen(exp);

    // reverse string
    reverse(exp);
    //change brackets
    brackets(exp);
    //get postfix
    getPostfix(exp);
    // reverse string again
    reverse(exp);
}

int main()
{    
    printf("The infix is: ");

    char expression[] = "((a/b)+c)-(d+(e*f))"; 
    printf("%s\n",expression);
    InfixtoPrefix(expression); 

    printf("The prefix is: ");
    printf("%s\n",expression);

    return 0; 
}

Output

The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*ef