Learn How To Evaluate Prefix Expression using Stack in C Programming Language. The Prefix notation is also known as Polish Notation. Before you proceed further with this code, you must know the complete operations of stack data structure.
Prefix To Infix Conversion Example
Prefix Expression: +22
Evaluation: 4
C Program To Evaluate Prefix Expression using Stack Data Structure
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 | #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define LIMIT 500 typedef struct prefix_expression { int top; int stack[LIMIT]; }stack_structure; void initialize(stack_structure *temp) { temp->top = -1; } void push(stack_structure *temp, int num) { if(temp->top == LIMIT) { printf("\nStack Overflow\n"); exit(-1); } else { temp->top++; temp->stack[temp->top]=num; } } int pop(stack_structure *temp) { int num; if(temp->top < 0) { printf("\nStack Underflow\n"); exit(-1); } num = temp->stack[temp->top]; temp->top--; return num; } int top(stack_structure *temp) { return temp->stack[0]; } void evaluate_prefix(stack_structure *temp, char operator, int x, int y) { int result; switch(operator) { case '-': result = x - y; break; case '*': result = x * y; break; case '%': result = x % y; break; case '/': result = x / y; break; case '+': result = x + y; break; case '$': result = pow(x, y); break; } push(temp, result); } int find_operator(char ch) { switch(ch) { case '%': return 20; case '/': return 20; case '*': return 20; case '-': return 20; case '$': return 20; case '+': return 20; default : return 10; } } int main() { int x, y, element, length, count; char * expression; stack_structure expression_stack; initialize(&expression_stack); printf("\nEnter Prefix Expression:\t"); scanf("%s", expression); length = strlen(expression); for(count = length - 1; count >= 0; count--) { if(expression[count] == '\0' || expression[count] == ' ') { continue; } switch(find_operator(expression[count])) { case 20 : x = pop(&expression_stack); y = pop(&expression_stack); evaluate_prefix(&expression_stack, expression[count], x, y); break; case 10 : element = expression[count] - '0'; push(&expression_stack, element); break; } } if(expression_stack.top != 0) { printf("\nInvalid Expression!\n"); return -1; } printf("\nEvaluation of Prefix Expression:\t %d\n", top(&expression_stack)); return 0 ; } |
Output
In case you get any compilation errors or any doubts in this C Program For Prefix Expression Evaluation, let us know about it in the Comment Section below.