# Infix to Prefix Conversion using Stack in C ## 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*ef`as 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() {
}

// checking is stack is empty
int isEmpty() {
}

// 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
```