LAB CAT – 1
FALL SEMESTER - 2025
Course Title : Data Structures and Algorithms
Course Code : ISWE102P
Submitted By,
Name of the Student : AKSHAYA P
Registration Number : 24MIS0112
Slot : L55+L56
Programme : [Link]-Software Engineering
School : SCORE
Topic : Infix to Postfix conversion
Date : 31-08-2025
INFIX TO POSTFIX CONVERSION
ALGORITHM
1. Start
2. Scan the infix expression from left to right, one symbol at a time.
3. For each symbol:
a. Operand (A–Z, a–z, 0–9)
→ Directly add to postfix expression.
b. Left Parenthesis ‘(’
→ Push it onto the stack.
c. Right Parenthesis ‘)’
→ Pop operators from the stack and add them to the postfix expression until a left
parenthesis ‘(’ is encountered.
→ Discard both parentheses.
d. Operator (+, −,*, /, ^)
4. If the stack is not empty and the precedence of the operator on top of the stack is
greater than or equal to the current operator:
→ Pop operators from the stack and add them to the postfix expression.
5. Push the current operator onto the stack.
6. After scanning all symbols:
→ Pop all remaining operators from the stack and add them to the postfix expression.
7. End
CODE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char stack[MAX];
char infix[MAX], postfix[MAX];
int top = -1;
void push(char c);
char pop();
int isEmpty();
void inToPost();
int space(char c);
void print();
int precedence(char symbol);
int main() {
printf("Enter the infix expression: ");
fgets(infix, MAX, stdin);
inToPost();
print();
return 0;
}
void inToPost() {
int i, j = 0;
char symbol, next;
for (i = 0; i < strlen(infix); i++) {
symbol = infix[i];
// if symbol is not whitespace
if (!space(symbol)) {
switch (symbol) {
case '(':
push(symbol);
break;
case ')':
while (!isEmpty() && (next = pop()) != '(') {
postfix[j++] = next;
}
break;
case '+':
case '-':
case '*':
case '/':
case '^':
while (!isEmpty() && precedence(stack[top]) >=
precedence(symbol)) {
postfix[j++] = pop();
}
push(symbol);
break;
default:
postfix[j++] = symbol;
}
}
}
// pop remaining operators
while (!isEmpty()) {
postfix[j++] = pop();
}
postfix[j] = '\0';
}
int space(char c) {
if (c == ' ' || c == '\t')
return 1;
return 0;
}
int precedence(char symbol) {
switch (symbol) {
case '^': return 3;
case '*':
case '/': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}
void print() {
int i = 0;
printf("The equivalent postfix expression is: ");
while (postfix[i] != '\0' ) {
printf("%c", postfix[i++]);
}
printf("\n");
}
void push(char c) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = c;
}
char pop() {
if (top == -1) {
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
int isEmpty() {
return (top == -1);
}
OUTPUT