If you are looking for a method to convert infix to a postfix program in C language, then you have arrived on the right page. In today’s blog, we’ll discuss a simple program to help you know how you can convert infix expressions to postfix expressions. Now, let’s understand all the concepts.
What is Infix Expression?
As the name implies, any mathematical form of expression that we notice is called infix notation. In infix form, an operator is mentioned in between two operands. For example, an expression in this: A*(B+C)/D is in infix form. It can be easily decoded as Add B and C, then multiply the outcome by A and then divide it by D for the final result.
What is Postfix Expression?
In postfix expression, an operator is seen after its operands. This is also called “Reverse Polish Notation”. The above expression can be written in the postfix expression as ABC+*D/.
Infix to Postfix Examples
Infix Expression: A*(B+C)/D
Postfix Expression: ABC+*D/
Algorithm to Convert Infix to Postfix Program in C
Scan the expression from left to right.
Just print the output if the scanned character is an operand.
Else
If the operand’s precedence is higher than the operator’s precedence, the stack (or stack is empty or has’(‘), then the operator needs to be pushed in the stack.
Else, pop all the operators that have higher or equal precedence than the scanned operator. After popping them, push this scanned operator.
If the scanned character is an ‘(‘, then it should be pushed into the stack.
If the scanned character is an ‘)’, pop the stack and print it until a ‘(‘ is encountered, and discard both the parenthesis.
Now, repeat steps 2 -6 until the whole infix.
Print output until the stack is not empty.
Method 1: Converting Infix Expression to Postfix using an Array-Based Stack
#include <limits.h> #include <stdio.h> #include <stdlib.h> #define MAX 20 char stackk[20]; int topp=-1; int isEmpty() { return topp == -1; } int isFull() { return topp == MAX – 1; } char peek() { return stackk[topp]; } char pop() { if(isEmpty()) return -1; char ch = stackk[topp]; topp–; return(ch); } void push(char oper) { if(isFull()) printf(“Stack Full!!!!”); else{ topp++; stackk[topp] = oper; } } int checkIfOperand(char ch) { return (ch >= ‘a’ && ch <= ‘z’) || (ch >= ‘A’ && ch <= ‘Z’); } int precedence(char ch) { switch (ch) { case ‘+’: case ‘-‘: return 1; case ‘*’: case ‘/’: return 2; case ‘^’: return 3; } return -1; } int covertInfixToPostfix(char* expression) { int i, j; for (i = 0, j = -1; expression[i]; ++i) { if (checkIfOperand(expression[i])) expression[++j]= expression[i]; else if (expression[i] == ‘(‘) push(expression[i]); else if (expression[i] == ‘)’) { while (!isEmpty() && peek()!='(‘) expression[++j] = pop(); if (!isEmpty() && peek() != ‘(‘) return -1; else pop(); } else { while (!isEmpty() && precedence(expression[i]) <= precedence(peek())) expression[++j] = pop(); push(expression[i]); }} while (!isEmpty()) expression[++j] = pop(); expression[++j] = ‘\0’; printf( “%s”, expression); } int main() { char expression[] = “((x+(y*z))-w)”; covertInfixToPostfix(expression); return 0; } |
Output: xyz*+w-
Method 2: Converting Infix to Postfix Expression Using a Struct-Based Stack
#include<stdio.h> #include <string.h> #include <limits.h> #include <stdlib.h> struct Stack { int topp; int maxSize; int* array; }; struct Stack* create(int max) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack -> maxSize = max; stack -> topp = -1; stack -> array = (int*)malloc(stack -> maxSize * sizeof(int)); return stack; }
int isFull(struct Stack* stack) { if(stack -> topp == stack -> maxSize – 1) { printf(“Will not be able to push maxSize reached\n”); } return stack -> topp== stack -> maxSize – 1; } int isEmpty(struct Stack* stack) { return stack -> topp== -1; } void push(struct Stack* stack, int item) { if (isFull(stack)) return; stack -> array[++stack -> topp] = item; } int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack -> array[stack -> topp–]; } int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->topp]; } int checkIfOperand(char ch) { return (ch >= ‘a’ && ch <= ‘z’) || (ch >= ‘A’ && ch <= ‘Z’); } int precedence(char ch) { switch (ch) { case ‘+’: case ‘-‘: return 1; case ‘*’: case ‘/’: return 2; case ‘^’: return 3; } return -1; } int covertInfixToPostfix(char* expression) { int i, j; struct Stack* stack= create(strlen(expression)); if(!stack) return -1; for (i = 0, j = -1; expression[i]; ++i) { if (checkIfOperand(expression[i])) expression[++j] = expression[i]; else if (expression[i] == ‘(‘) push(stack, expression[i]); else if (expression[i] == ‘)’) { while(!isEmpty(stack) && peek(stack) != ‘(‘) expression[++j] = pop(stack); if (!isEmpty(stack) && peek(stack) != ‘(‘) return -1; else pop(stack); } else { while(!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack))) expression[++j] = pop(stack); push(stack, expression[i]); } } while (!isEmpty(stack)) expression[++j] = pop(stack); expression[++j]=’\0′; printf( “%s”, expression); } int main() { char expression[] = “((x+(y*z))-w)”; covertInfixToPostfix(expression); return 0; } |
Output: xyz*+w-
Conclusion
Now that you know how to write a program in C for converting infix expression to postfix. Moreover, if you can’t code well, but you need a website, then you can reach us for website development services in Jalandhar.
Other Useful Links:–