Infix to prefix and evaluate prefix expression
Write a C Program to convert infix to prefix using stack and evaluate prefix expression. Here’s simple Program to convert infix to prefix using stack and evaluate prefix expression in C Programming Language.
What is Stack ?
Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.
Basic Operations : :
- push() − Pushing (storing) an element on the stack.
- pop() − Removing (accessing) an element from the stack.
- peek() − get the top data element of the stack, without removing it.
- isFull() − check if stack is full.
- isEmpty() − check if stack is empty.
Below is the source code for C Program to convert infix to prefix using stack and evaluate prefix expression which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* C Program to convert infix to prefix and evaluate 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 eval_pre();
char infix[MAX], prefix[MAX];
long int stack[MAX];
int top;
int isempty();
int white_space(char symbol);
void infix_to_prefix();
int priority(char symbol);
void push(long int symbol);
long int pop();
long int eval_pre();
int main()
{
long int value;
top = -1;
printf("Enter infix : ");
gets(infix);
infix_to_prefix();
printf("prefix : %s\n",prefix);
value=eval_pre();
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( !isempty( ) && priority(stack[top])> priority(symbol) )
prefix[p++] = pop();
push(symbol);
break;
default: /*if an operand comes*/
prefix[p++] = symbol;
}
}
}
while(!isempty( ))
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 isempty()
{
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 eval_pre()
{
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;
}/*End of eval_pre */
OUTPUT : :
/* C Program to convert infix to prefix and evaluate prefix expression */ ----------------------------------------------------------- Enter infix : A + B + C + D prefix : +++ABCD Stack underflow ------------------------------------------------------------ Enter infix : (9 + 8) * (5 + 6) prefix : *+98+56 Value of expression : 187 Process returned 0
If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.
Thanks for reading the post….