Data structure: Infix to Prefix Conversion
Infix to Prefix Conversion
In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep some rules. The Prefix and Postfix expression are quite understandable for the computers.
Algorithm
- Firstly, we reverse input expression.
- Then we scan input expression from left to right and repeat the steps which are given below for every element of input expression until the stack is Empty.
- If we encounter an operand then we add it in to the output expression.
- If we encounter the right parenthesis then we push it into the stack.
- If we encounter an operator then:
- We repeatedly check the precedence of incoming operator with the top of stack if the precedence of it is higher than the top of the stack then we simply add it into the stack else we pop the top of stack and add it into the output expression then again check the incoming operator precedence with the new top of stack.
- If precedence of incoming operator and top of the stack are same then check associativity rule.
- If we encounter left parenthesis then:
- We repeatedly pop the operators from the stack and add to the output expression until a right parenthesis is encountered.
- Remove the left parenthesis.
- Exit
Example
Input Expression: ( O ^ P ) * W / U / V * T + Q
Reversed I/P Expression: Q + T * V / U / W * ) P ^ O (
| Reversed I/P Expression | Stack | Output Expression |
| Q | Empty | Q |
| + | + | Q |
| T | + | Q T |
| * | + * | Q T |
| V | + * | Q T V |
| / | + * / | Q T V |
| U | + * / | Q T V U |
| / | + * / / | Q T V U |
| W | + * / / | Q T V U W |
| * | + * / / * | Q T V U W |
| ) | + * / / * ) | Q T V U W |
| P | + * / / * ) | Q T V U W P |
| ^ | + * / / * ) ^ | Q T V U W P |
| O | + * / / * ) ^ | Q T V U W P O |
| ( | + * / / * ) | Q T V U W P O ^ |
| + * / / * | Q T V U W P O ^ | |
| EMPTY | Q T V U W P O ^ * / / * + |
Reversed the O/P Expression: + * / / * ^ O P W U V T Q
C- Program to covert infix expression to prefix expression:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define BLANK ' '
#define TAB '\t'
#define MAX 50
long int pop();
long int pre_eval();
char infix[MAX], prefix[MAX];
long int stack[MAX];
int top;
int is_empty();
int white_space(char symbol);
void infix_to_prefix();
int priority(char symbol);
void push(long int symbol);
long int pop();
long int pre_eval();
int main()
{
long int value;
top = -1;
printf("Enter infix : ");
gets(infix);
infix_to_prefix();
printf("prefix : %s\n",prefix);
value=pre_eval();
printf("Value of expression : %ld\n",value);
return 0;
}/*End of main()*/
void infix_to_prefix()
{
int i,j,p,n;
char next ;
char symbol;
char temp;
n=strlen(infix);
p=0;
for(i=n-1; i>=0; i--)
{
symbol=infix[i];
if(!white_space(symbol))
{
switch(symbol)
{
case ')':
push(symbol);
break;
case '(':
while( (next=pop()) != ')')
prefix[p++] = next;
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while( !is_empty( ) && priority(stack[top])> priority(symbol) )
prefix[p++] = pop();
push(symbol);
break;
default: /*if an operand comes*/
prefix[p++] = symbol;
}
}
}
while(!is_empty( ))
prefix[p++] = pop();
prefix[p] = '\0'; /*End prefix with'\0' to make it a string*/
for(i=0,j=p-1;i<j;i++,j--)
{
temp=prefix[i];
prefix[i]=prefix[j];
prefix[j]=temp;
}
}/*End of infix_to_prefix()*/
/* This function returns the priority of the operator */
int priority(char symbol )
{
switch(symbol)
{
case ')':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default :
return 0;
}/*End of switch*/
}/*End of priority()*/
void push(long int symbol)
{
if(top > MAX)
{
printf("Stack overflow\n");
exit(1);
}
else
{
top=top+1;
stack[top] = symbol;
}
}/*End of push()*/
long int pop()
{
if(top == -1 )
{
printf("Stack underflow \n");
exit(2);
}
return (stack[top--]);
}/*End of pop()*/
int is_empty()
{
if(top==-1)
return 1;
else
return 0;
}
int white_space(char symbol)
{
if(symbol==BLANK || symbol==TAB || symbol=='\0')
return 1;
else
return 0;
}/*End of white_space()*/
long int pre_eval()
{
long int a,b,temp,result;
int i;
for(i=strlen(prefix)-1;i>=0;i--)
{
if(prefix[i]<='9' && prefix[i]>='0')
push( prefix[i]-48 );
else
{
b=pop();
a=pop();
switch(prefix[i])
{
case '+':
temp=b+a; break;
case '-':
temp=b-a;break;
case '*':
temp=b*a;break;
case '/':
temp=b/a;break;
case '%':
temp=b%a;break;
case '^':
temp=pow(b,a);
}
push(temp);
}
}
result=pop();
return result;
}
Output: -