Topic: Stack-Application

1. Program to convert a Decimal number to Binary Number using stack.

#include<stdio.h>

#define SIZE 10

int stack[SIZE];

int top=-1;

int empty();

int full();

void push(int x);

void pop(int temp);

int main()

int n,remainder,temp;

printf("Enter a decimal number:");

scanf("%d",&n);

temp=n;

while(n!=0)

if(!full())

remainder = n%2;

n = n/2;

push(remainder);

}
 if(!empty())

pop(temp);

int full()

if(top==SIZE-1)

return 1;

else

return 0;

int empty()

if(top==-1)

return 1;

else

return 0;

}
void push(int x)

if(full())

printf("Stack overflow!!\n");

else

top++;

stack[top] = x;

void pop(int temp)

if(empty())

printf("Stack empty");

else

printf("Binary equivalent of %d is :",temp);

for(int i=top;i>=0;i--)

printf("%d ",stack[top]);

top--;

}
output:

1. Enter a decimal number:12

Binary equivalent of 12 is :1 1 0 0

2. Enter a decimal number:13

Binary equivalent of 13 is :1 1 0 1

2. Program to check for balanced parenthesis using stack.

 Stack application 2- check for balanced parenthesis in an infix expression

#include<stdio.h>

#include<stdlib.h>

#define max 50

void main()

char stk[max],exp[100];

int top,i;

top = -1;

printf("\nEnter an infix expression\n");

gets(exp);

for(i=0; exp[i] != '\0'; i++)

if(exp[i]=='(' || exp[i] =='[' || exp[i] == '{' )

top++;

stk[top]= exp[i];

else if(exp[i] == ')')

{

if(stk[top] == '(')

{ top--;}

else

printf("Unbalanced expression\n");

exit(0);

if(exp[i] == ']')

if(stk[top] == '[')

{top--;}

else

printf("Unbalanced expression\n");

exit(0);

if(exp[i] == '}')

if(stk[top] == '{')

{ top--;}

else

printf("Unbalanced expression\n");

exit(0);

}
 }

if(top == -1)

printf("Expression is balanced\n");

else

printf("Exp is not balanced");

Output:

Enter an infix expression

((a/b)+(b*c))

Expression is balanced

3. Program to find the factorial of a number using stack.

Stack application 3- Working of recursion using stack.

#include<stdio.h>
#define MAX 100

int push(int *s,int top,int i)

{
if (top == MAX-1)
{
printf("\nStack Overflow");
}
else
{
top=top+1;
s[top] = i;
}
return top;
}

int pop(int *s, int *top)

{
if (*top >= 0)
{
 int ele = s[*top];
*top = *top - 1;
return ele;
}
else
{
printf("Stack underflow\n");
return 0;
}
}

void main()
{
int n, i, ans = 1, top = -1, s[MAX];
printf("\nEnter number: ");
scanf("%d",&n);
if(n<0)
{
printf("\nThe number can not be less than 0");
}
else
{
for(i = n ; i >0 ; i--)
{
top = push(s,top,i);
}
while(top>=0)
{
ans = ans * pop(s,&top);
}
printf("\nFactorial (%d) = %d\n",n,ans);
}

Output:

Enter number: 5

Factorial (5) = 120

4. Program to convert an input Infix expression to postfix expression using stack

#include<stdio.h>

#define SIZE 50

#include <ctype.h>

char s[SIZE];

int top=-1;

void push(char ele)

s[++top]=ele;

char pop()

return(s[top--]);

int priority(char ele)

switch(ele)

case '#': return 0;

case '(': return 1;

case '+':

case '-': return 2;

case '*':

case '/': return 3;

void main()
{

char I[50],P[50],ch,ele;

int i=0,k=0;

printf("\nEnter the Infix Expression\n");

scanf("%s",I);

push('#');

while( (ch=I[i++]) != '\0')

if( ch == '(') push(ch);

else

if(isalnum(ch)) P[k++]=ch;

else

if( ch == ')')

while( s[top] != '(')

P[k++]=pop();

ele=pop();

else

while( priority(s[top]) >= priority(ch) )

P[k++]=pop();

push(ch);

while( s[top] != '#')

P[k++]=pop();

P[k]='\0';

printf("\nGiven Infix Expn is: %s\nPostfix Expn is: %s\n",I,P);

}

OUTPUT:

1. Enter the Infix Expression

a+(b*c)

Given Infix Expn is: a+(b*c)

Postfix Expn is: abc*+

2. Enter the Infix Expression

(a+b)*(c/d)+(e-f)

Stack: #

Postfix: ab+cd/*ef-+

Given Infix Expn is: (a+b)*(c/d)+(e-f)

Postfix Expn is: ab+cd/*ef-+

Expression: a+(b*c)

Step-by-Step Conversion

Input Postfix
Step Action Stack
Char Output
0 – Push # initially [#] –
1 a Operand → Add to output [#] a
2 + Operator → Push (nothing higher on stack) [#,+] a
3 ( Push (always push left bracket) [#,+,(] a
4 b Operand → Add to output [#,+,(] ab

*
Operator → Push (stack top is (, lower [#,+,(,*] ab
5
priority)
6 c Operand → Add to output [#,+,(,*] abc

)
Pop until ( found → Pop * to output, then [#,+] abc*
7
discard (
8 End Pop remaining operators → Pop + [#] abc*+

Final Postfix: abc*+

Expression: (a+b)*(c/d)+(e-f)

Step-by-Step Table
Step Char Action Stack Postfix
0 – Push # [#] –
1 ( Push [#,(] –
2 a Add to postfix [#,(] a
3 + Push [#,(,+] a
4 b Add to postfix [#,(,+] ab
5 ) Pop until ( → Pop + to postfix [#] ab+
6 * Push [#,*] ab+
7 ( Push [#,*,(] ab+
8 c Add to postfix [#,*,(] ab+c
9 / Push [#,*,(,/ ] ab+c
10 d Add to postfix [#,*,(,/ ] ab+cd
11 ) Pop until ( → Pop / to postfix [#,*] ab+cd/

+
Pop * (higher priority) to postfix, [#,+] ab+cd/*
12
then push +
13 ( Push [#,+,(] ab+cd/*
14 e Add to postfix [#,+,(] ab+cd/*e
15 - Push [#,+,(,-] ab+cd/*e
16 f Add to postfix [#,+,(,-] ab+cd/*ef
17 ) Pop until ( → Pop - to postfix [#,+] ab+cd/*ef-
18 End Pop remaining operators → Pop + [#] ab+cd/*ef-+

Final Postfix: ab+cd/*ef-+

5. Postfix expression evaluation

#include <stdio.h>

#include <ctype.h> // for isdigit()

#define SIZE 50

int stack[SIZE];

int top = -1;

void push(int ele) {

stack[++top] = ele;

int pop() {

return stack[top--];

int main() {

char P[50];

int i = 0;

int op1, op2, res;

printf("\nEnter the Postfix Expression: ");

scanf("%s", P);

while (P[i] != '\0') {

char ch = P[i];

if (isdigit(ch)) {

// convert char to int and push

push(ch - '0');

else {

// Pop two operands

op2 = pop();

op1 = pop();

switch (ch) {

case '+': res = op1 + op2; break;

 case '-': res = op1 - op2; break;

case '*': res = op1 * op2; break;

case '/': res = op1 / op2; break;

push(res);

i++;

printf("\nResult of Postfix Evaluation: %d\n", pop());

return 0;

EXAMPLE: 23*54*+9-

Step Symbol Stack (top at right) Action

1 2 [2] Push 2
2 3 [2,3] Push 3
3 * [6] Pop 3,2 → 2×3=6 → Push
4 5 [6,5] Push 5
5 4 [6,5,4] Push 4
6 * [6,20] Pop 4,5 → 5×4=20 → Push
7 + [26] Pop 20,6 → 6+20=26 → Push
8 9 [26,9] Push 9
9 - [17] Pop 9,26 → 26-9=17 → Push
Infix to Prefix conversion

Example Step Expression / Action Result

(A + B) * (C - D) 1 Reverse infix (D - C) * (B + A)

2 Swap brackets (D - C) * (B + A)

3 Postfix of reversed expression DC-BA+*

4 Reverse postfix *+AB-CD

Prefix *+AB-CD

Example Step Expression / Action Result

A * (B + C) 1 Reverse infix (C + B) * A

2 Swap ( and ) (C + B) * A

3 Convert to postfix CB+ A*

4 Reverse postfix *A+CB

Prefix *A+CB

Example Step Expression / Action Result

(A + B) / (C + D) 1 Reverse infix (D + C) / (B + A)

2 Swap brackets (D + C) / (B + A)

3 Convert to postfix DC+BA+/

4 Reverse postfix /+AB+CD

Prefix /+AB+CD

Example Step Expression / Action Result

A - B * (C + D) 1 Reverse infix (D + C) * B - A

2 Swap brackets (D + C) * B - A
Example Step Expression / Action Result

3 Convert to postfix DC+ B* A-

4 Reverse postfix -A*B+CD

Prefix -A*B+CD

Infix to Prefix conversion program

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#define MAX 100

char stack[MAX];

int top = -1;

// Function to push element onto stack

void push(char c) {

stack[++top] = c;

// Function to pop element from stack

char pop() {

return stack[top--];

// Function to return precedence of operators

int precedence(char c) {

switch(c) {

case '+':
 case '-': return 1;

case '*':

case '/': return 2;

case '^': return 3;

return -1;

// Function to check if character is operator

int isOperator(char c) {

return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');

// Function to reverse a string and swap brackets

void reverse(char* exp) {

int i, j;

char temp;

int len = strlen(exp);

for (i = 0, j = len - 1; i < j; i++, j--) {

temp = exp[i];

exp[i] = exp[j];

exp[j] = temp;

for (i = 0; i < len; i++) {

if (exp[i] == '(')

exp[i] = ')';

else if (exp[i] == ')')

 exp[i] = '(';

// Convert infix to postfix

void infixToPostfix(char* infix, char* postfix) {

int i, k = 0;

char c;

for (i = 0; infix[i] != '\0'; i++) {

c = infix[i];

if (isalnum(c)) { // if operand

postfix[k++] = c;

else if (c == '(') {

push(c);

else if (c == ')') {

while (top != -1 && stack[top] != '(')

postfix[k++] = pop();

pop(); // remove '(' from stack

else if (isOperator(c)) {

while (top != -1 && precedence(stack[top]) >= precedence(c))

postfix[k++] = pop();

push(c);

while (top != -1)

 postfix[k++] = pop();

postfix[k] = '\0';

int main() {

char infix[MAX], postfix[MAX];

printf("Enter Infix Expression: ");

scanf("%s", infix);

// Step 1: Reverse and swap brackets

reverse(infix);

// Step 2: Convert to postfix

infixToPostfix(infix, postfix);

// Step 3: Reverse postfix to get prefix

reverse(postfix);

printf("Prefix Expression: %s\n", postfix);

return 0;

Prefix expression evaluation program

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <math.h>
#define MAX 100

int stack[MAX];

int top = -1;

void push(int value) {

stack[++top] = value;

int pop() {

return stack[top--];

// Function to evaluate prefix expression

int evaluatePrefix(char* prefix) {

int i, op1, op2, result;

// Start scanning from right to left

for (i = strlen(prefix) - 1; i >= 0; i--) {

char c = prefix[i];

if (isdigit(c)) {

// Convert char digit to int and push

push(c - '0');

else {

// Pop two operands from stack

op1 = pop();
 op2 = pop();

switch(c) {

case '+': result = op1 + op2; break;

case '-': result = op1 - op2; break;

case '*': result = op1 * op2; break;

case '/': result = op1 / op2; break;

case '^': result = pow(op1, op2); break;

default:

printf("Invalid operator: %c\n", c);

return -1;

push(result);

return pop();

int main() {

char prefix[MAX];

printf("Enter Prefix Expression (single-digit operands): ");

scanf("%s", prefix);

int value = evaluatePrefix(prefix);

printf("Result of Prefix Expression: %d\n", value);

return 0;

}
  Prefix Expression: +9*26

 Scan Right to Left:

1. Read 6 → push 6

2. Read 2 → push 2

3. Read * → pop 2 and 6 → multiply → push 12

4. Read 9 → push 9

5. Read + → pop 9 and 12 → add → push 21

Final Answer = 21

−+7∗45+20

Step Symbol Read (Right → Left) Action Stack (Top at Right)

1 0 Operand → Push 0 0

2 2 Operand → Push 2 20

3 + Operator → Pop(2,0) → 2+0=2 → Push 2 2

4 5 Operand → Push 5 25

5 4 Operand → Push 4 254

6 * Operator → Pop(4,5) → 4×5=20 → Push 20 2 20

7 7 Operand → Push 7 2 20 7

8 + Operator → Pop(7,20) → 7+20=27 → Push 27 2 27

25
9 - Operator → Pop(27,2) → 27-2=25 → Push 25
Program to check for duplicate parenthesis

#include <stdio.h>

#include <string.h>

int hasDuplicateParentheses(char *expr) {

char stack[100];

int top = -1, i;

for (i = 0; expr[i] != '\0'; i++) {

if (expr[i] == ')') {

int count = 0;

// Pop until '('

while (top >= 0 && stack[top] != '(') {

top--;

count++;

// Pop '(' itself

if (top >= 0) top--;

// If no elements between '(', ')', it's duplicate

if (count < 1) return 1;

} else {

stack[++top] = expr[i];

return 0;

}
int main() {

char expr1[] = "((a+b))";

char expr2[] = "(a+(b)/c)";

char expr3[] = "((a+(b)))";

printf("%s => %s\n", expr1, hasDuplicateParentheses(expr1) ? "Duplicate" : "No Duplicate");

printf("%s => %s\n", expr2, hasDuplicateParentheses(expr2) ? "Duplicate" : "No Duplicate");

printf("%s => %s\n", expr3, hasDuplicateParentheses(expr3) ? "Duplicate" : "No Duplicate");

return 0;