Learn how to convert an expression from Infix to Postfix using Stack in C Programming. This code for infix to postfix in c uses two arrays to store infix and postfix expression and a stack for conversion from infix to postfix expression.
What is Polish Notation?
A polish mathematician named Jan Lukasiewicz has given a method to represent arithmetic expressions. It included infix, postfix and prefix methods to represent an expression. The infix method is the conventional method to represent arithmetic expressions since it is better analyzed by the computers.
Infix To Postfix Conversion Example
Infix String: A+ B ^ C + D * E / (F + G)
Postfix String: ABC/+DE*_F+
Steps To Convert Infix Expression to Postfix Expression
- Scan the symbols of the Infix string from left to right one by one.
- If the character is an operand then shift it to the postfix string (array).
- If the character is left parathesis then push it on the stack.
- If the character found is right parantheses then pop all the operators from the stack upto the first left parantheses and add all these operators to the postfix string. Now, delete the right and left parantheses.
- If the character is an operator then pop the operators that have the greater or equal precedence than the character operator and shift these popped operators to the postfix string. Now, push the scanned symbol operator on the stack.
- After all the characters of the Infix string have been scanned, pop all the remaining operators on the stack and then shift them to postfix string.
C Program For Infix To Postfix Conversion using Stack
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 | #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> void expression_conversion(); int check_space_tabs(char character); void push(long int character); int pop(); int priority(char character); int isEmpty(); int top; long int stack[50]; char infix_expression[50], postfix_expression[50]; int main() { top = -1; printf("\nEnter an Expression in Infix format:\t"); scanf("%[^\n]s", infix_expression); expression_conversion(); printf("\nExpression in Postfix Format: \t%s\n", postfix_expression); return 0; } void expression_conversion() { unsigned int count, temp = 0; char next; char character; for(count = 0; count < strlen(infix_expression); count++) { character = infix_expression[count]; if(!check_space_tabs(character)) { switch(character) { case '(': push(character); break; case ')': while((next = pop()) != '(') { postfix_expression[temp++] = next; } break; case '+': case '-': case '*': case '/': case '%': case '^': while(!isEmpty() && priority(stack[top]) >= priority(character)) postfix_expression[temp++] = pop(); push(character); break; default: postfix_expression[temp++] = character; } } } while(!isEmpty()) { postfix_expression[temp++] = pop(); } postfix_expression[temp] = '\0'; } int priority(char character) { switch(character) { case '(': return 0; case '+': case '-': return 1; case '*': case '/': case '%': return 2; case '^': return 3; default: return 0; } } void push(long int character) { if(top > 50) { printf("Stack Overflow\n"); exit(1); } top = top + 1; stack[top] = character; } int check_space_tabs(char character) { if(character == ' ' || character == '\t') { return 1; } else { return 0; } } int pop() { if(isEmpty()) { printf("Stack is Empty\n"); exit(1); } return(stack[top--]); } int isEmpty() { if(top == -1) { return 1; } else { return 0; } } |
Output
In case you get any compilation errors or any doubts in this C Program For Conversion of Infix Expression to Postfix Expression, let us know about it in the Comment Section below.
Best Program. Can we convert infix expression to postfix expression using linked list in c?
this program is too much difficult ..plz give me the concept about how to convert a infix to prefix or postfix