ASSIGNMENT - 9
DATE : 09/12/2024
9. Write a program to convert infix notation into postfix, prefix notations.
Algorithm:
Step 1: Start
Step2: Algorithm to Convert Infix to Postfix
2.1: Initialize an empty stack for operators and an empty string for the postfix
expression.
2.3: Read the infix expression from left to right one symbol at a time:
2.3.1: Operand (A-Z, 0-9) → Append it to the postfix expression.
2.3.2: Left parenthesis '(' → Push it onto the stack.
2.3.3: Right parenthesis ')' → Pop from the stack and append to postfix until '(' is
found. Discard '('.
*Operator (+, -, , /, ^).While the stack is not empty and the precedence of the top
operator is greater than or equal to the current operator, pop from the stack and
append it to postfix.
Push the current operator onto the stack.
Step3: After scanning the expression, pop all remaining operators from the stack
and append them to the postfix expression.
Step4: End – The final postfix expression is obtained.
Step5: Algorithm to Convert Infix to Prefix
5.1: Reverse the infix expression (Read from right to left). Swap '(' with ')' and vice
versa.
5.2: Use the postfix conversion algorithm on the reversed expression to get an
intermediate postfix expression.
5.3: Reverse the postfix expression to get the final prefix expression.
Step6: End – The final prefix expression is obtained.
Source Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
typedef struct {
char arr[MAX];
int top;
} Stack;
typedef struct {
char arr[MAX][MAX];
int top;
} StringStack;
void initStack(Stack *s) {
s->top = -1;
int isEmpty(Stack *s) {
return s->top == -1;
int isFull(Stack *s) {
return s->top == MAX - 1;
void push(Stack *s, char ch) {
if (!isFull(s)) {
s->arr[++(s->top)] = ch;
char pop(Stack *s) {
if (!isEmpty(s)) {
return s->arr[(s->top)--];
return '\0';
char peek(Stack *s) {
if (!isEmpty(s)) {
return s->arr[s->top];
return '\0';
void initStringStack(StringStack *s) {
s->top = -1;
void pushString(StringStack *s, char *str) {
if (s->top < MAX - 1) {
strcpy(s->arr[++(s->top)], str);
void popString(StringStack *s, char *result) {
if (s->top >= 0) {
strcpy(result, s->arr[(s->top)--]);
int precedence(char ch) {
switch (ch) {
case '+':
case '-': return 1;
case '*':
case '/': return 2;
case '^': return 3;
default: return 0;
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i, j = 0;
for (i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
else if (ch == '(') {
push(&s, ch);
else if (ch == ')') {
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[j++] = pop(&s);
pop(&s);
else if (isOperator(ch)) {
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(ch)) {
postfix[j++] = pop(&s);
push(&s, ch);
while (!isEmpty(&s)) {
postfix[j++] = pop(&s);
}
postfix[j] = '\0';
void infixToPrefix(char *infix, char *prefix) {
Stack s;
StringStack strStack;
initStack(&s);
initStringStack(&strStack);
int i, length = strlen(infix);
for (i = length - 1; i >= 0; i--) {
char ch = infix[i];
if (isalnum(ch)) {
char operand[2] = {ch, '\0'};
pushString(&strStack, operand);
else if (ch == ')') {
push(&s, ch);
else if (ch == '(') {
while (!isEmpty(&s) && peek(&s) != ')') {
char op = pop(&s);
char op1[MAX], op2[MAX];
popString(&strStack, op1);
popString(&strStack, op2);
char temp[MAX];
sprintf(temp, "%c%s%s", op, op2, op1);
pushString(&strStack, temp);
pop(&s);
else if (isOperator(ch)) {
while (!isEmpty(&s) && precedence(peek(&s)) > precedence(ch)) {
char op = pop(&s);
char op1[MAX], op2[MAX];
popString(&strStack, op1);
popString(&strStack, op2);
char temp[MAX];
sprintf(temp, "%c%s%s", op, op2, op1);
pushString(&strStack, temp);
push(&s, ch);
while (!isEmpty(&s)) {
char op = pop(&s);
char op1[MAX], op2[MAX];
popString(&strStack, op1);
popString(&strStack, op2);
char temp[MAX];
sprintf(temp, "%c%s%s", op, op2, op1);
pushString(&strStack, temp);
popString(&strStack, prefix);
int main() {
char infix[MAX], postfix[MAX], prefix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
infixToPrefix(infix, prefix);
printf("Postfix expression: %s\n", postfix);
printf("Prefix expression: %s\n", prefix);
return 0;
Output:
