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 : :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
/* 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 : :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
/* 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….