Infix to Prefix using stack
In this tutorial, we will learn what is mean by infix and prefix conversion and how to convert infix to prefix using stack.
Infix expression : Infix expression is an expression which contains the operator in between to operands.
Example: A+B
Prefix expression : Prefix expression is an expression which contains operator first and then the operands.
Example: +AB
As above we have seen the infix and prefix expression we convert an infix expression into prefix expression using stack.
How to convert infix to prefix : we have two technic to convert infix to prefix.
Infix to prefix using stack :
- First, we take infix expression.
- We read the expression from left to right.
- We read this expression one by one and check whether it is operand or operator.
- If it is operator then we print it and if operands we store it into the stack.
- In the end, we retrieve operands from a stack and print it.
Logic 2 :
- First, we take infix expression.
- We read the expression from left to right.
- Convert it to postfix expression store it stack.
- then retrieve element one by one and print
- You will get prefix expression.
Infix to postfix example : Convert following infix expression to prefix expression.
Infix expression: A+B
Prefix expression: +AB
Infix to postfix algorithm
1. Start
2. Declare variable
3. Read infix input
4. Convert infix to prefix
5. Print prefix expression
6. Endinfixto prefix c
Program to convert infix to prefix using stack
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254 | #include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>int pop();int priority(char symbol);int isEmpty();void infix_to_prefix();int check(char symbol);void push(long int symbol);char prefix_string[20], infix_string[20], postfix_string[20];int top;long int stack[20];int main(){int count, size;char temp;top = -1;printf(“\nEnter an Expression in Infix format:\t”);scanf(“%[^\n]s”, infix_string);infix_to_prefix();printf(“\nExpression in Postfix Format: \t%s\n”, postfix_string);size = strlen(postfix_string) – 1;strncpy(prefix_string, postfix_string, 20);for(count = 0; count < size; count++, size–){temp = prefix_string[count];prefix_string[count] = prefix_string[size];prefix_string[size] = temp;}printf(“\nExpression in Prefix Format: \t%s\n”, prefix_string);return 0;}void infix_to_prefix(){unsigned int count, temp = 0;char next;char symbol;for(count = 0; count < strlen(infix_string); count++){symbol = infix_string[count];if(!check(symbol)){switch(symbol){case ‘(‘: push(symbol);break;case ‘)’:while((next = pop()) != ‘(‘){postfix_string[temp++] = next;}break;case ‘+’:case ‘-‘:case ‘*’:case ‘/’:case ‘%’:case ‘^’:while(!isEmpty() && priority(stack[top]) >= priority(symbol))postfix_string[temp++] = pop();push(symbol);break;default:postfix_string[temp++] = symbol;}}}while(!isEmpty()){postfix_string[temp++] = pop();}postfix_string[temp] = ‘\0’;}int priority(char symbol){switch(symbol){case ‘(‘: return 0;case ‘+’:case ‘-‘:return 1;case ‘*’:case ‘/’:case ‘%’:return 2;case ‘^’:return 3;default:return 0;}}int check(char symbol){if(symbol == ‘\t’ || symbol == ‘ ‘){return 1;}else{return 0;}}void push(long int symbol){if(top > 20){printf(“Stack Overflow\n”);exit(1);}top = top + 1;stack[top] = symbol;}int isEmpty(){if(top == -1){return 1;}else{return 0;}}int pop(){if(isEmpty()){printf(“Stack is Empty\n”);exit(1);}return(stack[top–]);} |
Output :
Explanation :
1. Start with writing the header file in program.
2. Declare variables.
3. Take input infix expression.
4. Convert Infix to postfix expression
5. Then convert postfix expression to prefix expression.
7. print prefix expression.