Table of Contents
In this guide, we will see about Infix to postfix conversion in C.
In the computer, all the arithmetic expressions first convert to their postfix from infix. After the conversion, the evaluation will start.
Algorithm
- First, we have to fix the precedence of the expression.
- To convert the infix expression to its postfix expression, we have to take care of the following conditions:
-
- If the characters are in between 0-9 or a-z or A-Z, then we insert them to another array.
- If there is “ ( ” then we simply insert it into the stack.
- If there is “ ) ” then we pop the element from the stack until we get the “ ( ”.
- If there is some operator like +, -, *, / , then check the precedence of that operator to the top element of the stack. If the precedence of the operator is less than the top element of stack then we pop that element from the stack and insert it into another array. Otherwise, push that operator into the stack.
-
- After all of this condition if the stack remains not empty, then we have to pop all the elements from the stack until it becomes empty
Implementation:
|
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 |
#include<stdio.h> #include <stdlib.h> #include<stdbool.h> struct node{ char data; struct node* next; }; //to check is the stack empty or not bool is_empty(struct node* st){ if(st==NULL){ return true; } return false; } // Create a new node struct node* create_node(char x){ struct node* temp=(struct node*)malloc(sizeof(struct node)); temp->data=x; temp->next=NULL; return temp; } //enter a character in the front of the stack void push(struct node** st,char x){ struct node* temp=create_node(x); temp->next=*st; *st=temp; } //pop the first element fom the stack void pop(struct node** st){ struct node* temp=*st; *st=temp->next; } //give the top element of the stack char top_ele(struct node* st){ return st->data; } //Return the precedence of the operator int precedence(char ch){ if(ch=='^') return 3; else if(ch=='/' || ch=='*') return 2; else if(ch=='+'|| ch=='-') return 1; else return 0; } //Function to conver infix expression to postfix void infix_to_postfix(char* str,char* new_str,int len){ int j=0; struct node* st=NULL; for(int i=0;i<len;i++){ if((str[i]>='0' && str[i]<='9')||(str[i]>='a' && str[i]<='z')){ new_str[j++]=str[i]; } else if(str[i]=='('){ push(&st,str[i]); } else if(str[i]==')'){ //pop the elements from the stack until the "(" comes while(!is_empty(st) && top_ele(st)!='('){ new_str[j++]=top_ele(st); pop(&st); } pop(&st); } else{ //check if the precedence of the top element of the stack is //greater than the current operator then pop the operator from the stack //continue check the condition while(!is_empty(st) && precedence(top_ele(st))>=precedence(str[i])){ new_str[j++]=top_ele(st); pop(&st); } push(&st,str[i]); } } //if the stack is not empty while(!is_empty(st)){ new_str[j++]=top_ele(st); pop(&st); } new_str[j]='\n'; } int main(){ int len; printf("Enter the length : "); scanf("%d",&len); printf("Enter the expression : "); char str[len],new_str[len]; scanf("%s",str); infix_to_postfix(str,new_str,len); printf("Postfix : "); printf("%s",new_str); return 0; } |
Output:
Enter the length : 23
Enter the expression : a+b*(c^d-e)/(f+g*h^s)-i
Postfix : abcd^e-*fghs^*+/+i-
Enter the expression : a+b*(c^d-e)/(f+g*h^s)-i
Postfix : abcd^e-*fghs^*+/+i-
That’s all about Infix to postfix conversion in C
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
