ASSIGNMENT WEEK – 4
Name – HIMANSHU RAJ
Register No. - EA2331201010152
Program - B.C.A.-Data Science
Subject – Data Structures and Algorithms
Semester – II Semester
EA2331201010152
1. Write a C program to evaluate infix expressions. An infix expression looks
like the following:
9 * (5 - 4) + 2 / 6
This program must first convert the infix expression to a postfix
expression, and then evaluate the postfix expression. A postfix
expression for the above infix expression looks like the following:
954-*26/+
For this assignment you will need to implement and apply one stack to
convert from infix to postfix, and implement and apply a second stack to
evaluate the postfix expression. Your program must take the infix
expression as a string from the user.
Ans. the C program to evaluate infix expressions, incorporating the best aspects of the
provided responses and addressing noted issues:
C
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
char stack[MAX_SIZE];
int top = -1;
// Function prototypes for clarity
void push(char);
char pop();
int isEmpty();
int precedence(char);
void infixToPostfix(char *infix, char *postfix);
int evaluatePostfix(char *postfix);
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin); // Use fgets to capture newline
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
int result = evaluatePostfix(postfix);
printf("Result: %d\n", result);
return 0;
}
void push(char op) {
if (top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
}
stack[++top] = op;
}
EA2331201010152
char pop() {
if (isEmpty()) {
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
int isEmpty() {
return top == -1;
}
// Handle spaces and ensure newline is removed
void infixToPostfix(char *infix, char *postfix) {
int i, j = 0;
char ch, popped;
for (i = 0; infix[i] != '\n'; i++) {
ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
} else if (ch == '(') {
push(ch);
} else if (ch == ')') {
while ((popped = pop()) != '(') {
postfix[j++] = popped;
}
} else {
while (!isEmpty() && precedence(stack[top]) >= precedence(ch)) {
postfix[j++] = pop();
}
push(ch);
}
}
while (!isEmpty()) {
postfix[j++] = pop();
}
postfix[j] = '\0'; // Terminate with null character
}
int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}
int evaluatePostfix(char *postfix) {
int i, op1, op2, result;
for (i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
push(postfix[i] - '0'); // Convert character to integer
} else {
op2 = pop();
op1 = pop();
switch (postfix[i]) {
case '+':
result = op1 + op2;
break;
case '-':
result = op1 - op2;
EA2331201010152
break;
case '*':
result = op1 * op2;
break;
case '/':
result = op1 / op2;
break;
}
push(result + '0'); // Convert integer to character
}
}
return pop() - '0'; // Convert character to integer
}
EA2331201010152
