Postfix notation - It is another way to represent operations or expressions, such as x y +, which is the equivalent of x + y in infix notation. The main concept is to move the operator to the right side of the operands.
In C, there is an algorithm for converting infix to postfix programs:
- Traversing the given expression from left to right should begin.
- Just output the scanned character if it is an operand.
- Else If the operand's precedence is greater than the operator's precedence in the stack (or the stack is empty or has'('), then push the operator into the stack. Else, Any operator with more or equal precedence than the traversed operator are popped. Push this scanned operator after you pop them. (Stop and push the scanned operator on the stack if we encounter a parenthesis during popping.)
- Push the scanned character to the stack if it is a '('.
- If the scanned character is a ')', pop the stack and output it until another '(' appears, then eliminate both the parentheses.
- Steps 2 through 6 should now be repeated until the entire infix, i.e. entire characters, is scanned.
- Printing results
- Pop and print until the stack is not empty.
- If the operand's precedence is greater than the operator's precedence in the stack (or the stack is empty or has'('), then push the operator into the stack.
- Else, Any operator with more or equal precedence than the traversed operator are popped. Push this scanned operator after you pop them. (Stop and push the scanned operator on the stack if we encounter a parenthesis during popping.)
Technique 1: Conversion of Infix to Postfix Using an Array-Based Stack
We will employ an array-backed stack method in this process.
Converting from Infix to Postfix in C Code:
Example
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
char stk[20];
int top = -1;
int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == MAX - 1;
}
char peek()
{
return stk[top];
}
char pop()
{
if(isEmpty())
return -1;
char ch = stk[top];
top--;
return(ch);
}
void push(char oper)
{
if(isFull())
printf("Stack Full!!!!");
else{
top++;
stk[top] = 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
Output
xyz*+w-
Technique 2: Conversion of Infix to Postfix Using a Struct-Based Stack
We will utilize a struct-based stack method in this process.
Converting from Infix to Postfix in C Code:
Example
#include<stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
struct Stack {
int top;
int maxSize;
int* array;
};
struct Stack* create(int max)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack -> maxSize = max;
stack -> top = -1;
stack -> array = (int*)malloc(stack -> maxSize * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{
if(stack -> top == stack -> maxSize - 1)
{
printf("Will not be able to push maxSize reached\n");
}
return stack -> top == stack -> maxSize - 1;
}
int isEmpty(struct Stack* stack)
{
return stack -> top == -1;
}
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack -> array[++stack -> top] = item;
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack -> array[stack -> top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
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
Output
xyz*+w-
Conclusion:
In this guide, we discussed the popular subject of transforming Infix notation to Postfix notation in the C programming language. This tutorial aims to enhance your comprehension of stacks and algorithmic design. Various companies such as TCS, Wipro, Samsung, Squad stack, and more often include these concepts in their interview assessments. Mastering these concepts can significantly enhance your programming skills.