Experiment : 7
Aim :
Write a program to solve the infix to postfix and find the value of the infix after solving
Programming Language & Tools
Language: C
IDE: VS Code
Compiler: GCC (GNU Compiler Collection)
Functions Overview
1. initStack(Stack *s)
Initializes the character stack.
Time Complexity: O(1)
Space Complexity: O(1)
2. initNumStack(NumStack *s)
Initializes the numeric stack.
Time Complexity: O(1)
Space Complexity: O(1)
3. isEmpty(Stack *s) / isNumEmpty(NumStack *s)
Checks whether the character/numeric stack is empty.
Time Complexity: O(1)
Space Complexity: O(1)
4. isFull(Stack *s)
Checks whether the character stack is full.
Time Complexity: O(1)
Space Complexity: O(1)
5. push(Stack *s, char c) / pushNum(NumStack *s, int num)
Pushes a character/integer onto the respective stack.
Time Complexity: O(1)
Space Complexity: O(1)
6. pop(Stack *s) / popNum(NumStack *s)
Pops and returns the top element from the character/numeric stack.
Time Complexity: O(1)
Space Complexity: O(1)
7. precedence(char op)
Returns precedence level of operators (+, -, *, /, ^).
Time Complexity: O(1)
Space Complexity: O(1)
8. isOperator(char c)
Checks if a character is a valid operator.
Time Complexity: O(1)
Space Complexity: O(1)
9. infixToPostfix(char *infix, char *postfix)
Converts an infix expression to postfix using a stack.
Time Complexity: O(n)
Space Complexity: O(n)
10. evaluatePostfix(char *postfix)
Evaluates a postfix expression using a numeric stack.
Time Complexity: O(n)
Space Complexity: O(n)
code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
// Stack structure
typedef struct {
char items[MAX];
int top;
} Stack;
// Numeric Stack structure
typedef struct {
int items[MAX];
int top;
} NumStack;
// Function to initialize stack
void initStack(Stack *s) {
s->top = -1;
// Function to initialize numeric stack
void initNumStack(NumStack *s) {
s->top = -1;
}
// Function to check if stack is empty
int isEmpty(Stack *s) {
return s->top == -1;
// Function to check if numeric k is empty
int isNumEmpty(NumStack *s) {
return s->top == -1;
// Function to check if stack is full
int isFull(Stack *s) {
return s->top == MAX - 1;
}
// Function to push an element
void push(Stack *s, char c) {
if (isFull(s)) {
printf("Stack Overflow\n");
return;
s->items[++s->top] = c;
// Function to push an element
void pushNum(NumStack *s, int num) {
if (s->top == MAX - 1) {
printf("Numeric Stack Overflow\n");
return;
s->items[++s->top] = num;
// Function to pop
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow\n");
return -1;
return s->items[s->top--];
int popNum(NumStack *s) {
if (isNumEmpty(s)) {
printf("Numeric Stack Underflow\n");
return -1;
return s->items[s->top--];
int precedence(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
if (op == '^')
return 3;
return 0;
}
// Function to check if the character is an operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
// Function to convert infix expression to postfix expression
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i, j = 0;
char c;
for (i = 0; infix[i] != '\0'; i++) {
c = infix[i];
if (isalnum(c)) {
postfix[j++] = c;
// If character is '(', push it to stack
else if (c == '(') {
push(&s, c);
else if (c == ')') {
while (!isEmpty(&s) && [Link][[Link]] != '(')
postfix[j++] = pop(&s);
pop(&s); // Remove '(' from stack
// If an operator is found
else if (isOperator(c)) {
while (!isEmpty(&s) && precedence([Link][[Link]]) >= precedence(c))
postfix[j++] = pop(&s);
push(&s, c);
// Pop all remaining operators from stack
while (!isEmpty(&s))
postfix[j++] = pop(&s);
postfix[j] = '\0';
// Function to evaluate a postfix expression
int evaluatePostfix(char *postfix) {
NumStack s;
initNumStack(&s);
int i, op1, op2, result;
for (i = 0; postfix[i] != '\0'; i++) {
char c = postfix[i];
if (isdigit(c)) {
pushNum(&s, c - '0');
else if (isOperator(c)) {
op2 = popNum(&s);
op1 = popNum(&s);
switch (c) {
case '+': result = op1 + op2; break;
case '-': result = op1 - op2; break;
case '*': result = op1 * op2; break;
case '/': result = op1 / op2; break;
case '^': result = 1;
for (int j = 0; j < op2; j++)
result *= op1;
break;
pushNum(&s, result);
return popNum(&s);
int main() {
char infix[MAX], postfix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
printf("Evaluation result: %d\n", evaluatePostfix(postfix));
return 0;}
Output: