Name : Brijesh M Barvaliya.
Roll No. : 24BCP312 / (G10)
DSA LAB : 5
1) Write a program to evaluate the following given postfix expressions:
a. 2 3 1 * + 9 – Output: -4
b. 2 2 + 2 / 5 * 7 + Output: 17
Code:::
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x)
stack[++top] = x;
int pop()
if (top == -1) {
printf("Error: Stack underflow\n");
exit(1);
return stack[top--];
int evaluatePostfix(char* exp)
{
char *token = strtok(exp, " ");
while (token != NULL)
if (isdigit(token[0]))
push(atoi(token));
else
int val2 = pop();
int val1 = pop();
switch (token[0])
case '+':
push(val1 + val2); break;
case '-':
push(val1 - val2); break;
case '*':
push(val1 * val2); break;
case '/':
push(val1 / val2); break;
default:
printf("Invalid operator: %s\n", token);
exit(1);
token = strtok(NULL, " ");
return pop();
}
int main()
char exp[MAX];
printf("Enter a postfix expression (tokens separated by space):\n");
gets(exp);
int result = evaluatePostfix(exp);
printf("Result = %d\n", result);
return 0;
Output:::
2) Write a program that convert the given infix expression into postfix expression using stack. Example-
Input: 𝑎 +𝑏 ∗(𝑐^𝑑 −𝑒)^(𝑓 +𝑔∗ℎ)−𝑖
Output: 𝑎𝑏𝑐𝑑^𝑒 − 𝑓𝑔ℎ ∗ +^∗+𝑖 –
Code:::
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char x)
stack[++top] = x;
char pop()
if (top == -1) return -1;
return stack[top--];
int precedence(char x)
if (x == '^') return 3;
if (x == '*' || x == '/') return 2;
if (x == '+' || x == '-') return 1;
return 0;
void infixToPostfix(char* exp)
char output[MAX];
int k = 0;
for (int i = 0; exp[i] != '\0'; i++)
{
char c = exp[i];
if (isalnum(c))
output[k++] = c;
else if (c == '(')
push(c);
else if (c == ')') {
while (top != -1 && stack[top] != '(')
output[k++] = pop();
pop();
else
while (top != -1 && precedence(stack[top]) >= precedence(c))
output[k++] = pop();
push(c);
while (top != -1)
output[k++] = pop();
}
output[k] = '\0';
printf("Postfix Expression: %s\n", output);
int main()
char exp[MAX];
printf("Enter an infix expression: ");
fgets(exp, MAX, stdin);
exp[strcspn(exp, "\n")] = '\0';
infixToPostfix(exp);
return 0;
OutPut:::
3) Given an expression, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]”
are correct in the expression or not.
Example:
Input: exp =“[( )]{ }{[( )( )]( )}” Output: Balanced
Input: exp =“[( ])” Output: Not Balanced
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c)
stack[++top] = c;
char pop()
if (top == -1)
return -1;
return stack[top--];
int isMatching(char a, char b)
return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
int checkBalanced(char* exp)
for (int i = 0; exp[i] != '\0'; i++)
char c = exp[i];
if (c == '(' || c == '{' || c == '[')
push(c);
else if (c == ')' || c == '}' || c == ']')
{
if (top == -1)
return 0;
char popped = pop();
if (!isMatching(popped, c))
return 0;
return (top == -1);
int main()
char exp[MAX];
printf("Enter an expression with brackets: ");
gets(exp);
exp[strcspn(exp, "\n")] = '\0';
if (checkBalanced(exp))
printf("Balanced Expression \n");
else
printf("Not Balanced \n");
return 0;
}
Output ::
