1.

Write a C program to implement a stack using arrays with push, pop

operations.

#include <stdio.h>
#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

void push(int data) {

if (top == MAX_SIZE - 1) {
printf("Overflow stack!\n");
return;
}
top++;
stack[top] = data;
}

int pop() {
if (top == -1) {
printf("Stack is empty!\n");
return -1;
}
int data = stack[top];
top--;
return data;
}

int main() {
push(1);
push(2);
push(3);
push(4);
push(5);
push(3);
 printf("Elements in the stack are: ");
while (top != -1) {
printf("%d ", pop());
}
printf("\n");
return 0;
}

2. Write a C program to implement a queue using arrays with push, pop

operations.

#include<stdio.h>
#define SIZE 5

//Basic value initialisation

int queue[SIZE], front = -1, rear = -1;

//Function created to handle enqueue

void enqueue(int item){
if(rear == SIZE-1){
printf("Can't enqueue as the queue is full\n");
}
else{
//The first element condition
if(front == -1){
front = 0;
}

rear = rear + 1;
queue[rear] = item;
printf("We have enqueued %d\n",item);
}
}

//Function created to handle dequeue

void dequeue(){
 if(front == -1){
printf("Can't dequeue as the queue is empty\n");
}
else{
printf("We have dequeued : %d\n", queue[front]);
front = front + 1;

//Only happens when the last element was dequeued

if(front > rear){
front = -1;
rear = -1;
}
}
}

//function to print the queue

void printQueue(){
if(rear == -1)
printf("\nUnable to display as queue is empty");
else{
int i;
printf("\nThe queue after enqueue & dequeue ops looks like :");

for(i = front; i <= rear; i++)

printf("%d ",queue[i]);
}
}

int main() {
//enqueue begins here
enqueue(2);
enqueue(4);
enqueue(6);
enqueue(8);

//dequeue beings here

dequeue();
dequeue();
 printQueue();
return 0;
}

3. Write a C program to check whether the brackets in the expression

are balanced or not using stack.

Example:

Input: exp = “[()]{}{[()()]()}”

Output: Balanced
Explanation: all the brackets are well-formed

Input: exp = “[(])”

Output: Not Balanced
Explanation: 1 and 4 brackets are not balanced because there is a
closing ‘]’ before the closing ‘(‘

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 30
int top=-1;
int stack[MAX];

void push(char);
char pop();
int match(char a,char b);
int check(char []);

int main()
{
char exp[MAX];
 int valid;
printf("Enter an algebraic expression : ");
gets(exp);
valid=check(exp);
if(valid==1)
printf("Valid expression\n");
else
printf("Invalid expression\n");

return 0;

int check(char exp[] )

{
int i;
char temp;
for(i=0;i<strlen(exp);i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
push(exp[i]);
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top==-1) /*stack empty*/
{
printf("Right parentheses are more than left
parentheses\n");
return 0;
}
else
{
temp=pop();
if(!match(temp, exp[i]))
{
printf("Mismatched parentheses are : ");
printf("%c and %c\n",temp,exp[i]);
return 0;
}
 }
}
if(top==-1) /*stack empty*/
{
printf("Balanced Parentheses\n");
return 1;
}
else
{
printf("Left parentheses more than right parentheses\n");
return 0;
}
}

int match(char a,char b)

{
if(a=='[' && b==']')
return 1;
if(a=='{' && b=='}')
return 1;
if(a=='(' && b==')')
return 1;
return 0;
}

void push(char item)

{
if(top==(MAX-1))
{
printf("Stack Overflow\n");
return;
}
top=top+1;
stack[top]=item;
}

char pop()
 {
if(top==-1)
{
printf("Stack Underflow\n");
exit(1);
}
return(stack[top--]);
}

4. Write a C program to reverse a string using stack.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

char stack[MAX_SIZE];
int top = -1;

void push(char data) {

if (top == MAX_SIZE - 1) {
printf("Overflow stack!\n");
return;
}
top++;
stack[top] = data;
}

char pop() {
if (top == -1) {
printf("Empty Stack!\n");
return '\0';
}
char data = stack[top];
top--;
return data;
}
 void reverse_string(char *str) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
push(str[i]);
}
for (int i = 0; i < len; i++) {
str[i] = pop();
}
}

int main() {
char text[MAX_SIZE];
printf("Input a string: ");
scanf("%s", text);
reverse_string(text);
printf("Reversed string using a stack is: %s\n", text);
return 0;
}

5. Write a C program to check whether a given string is palindrome or

not using stack.

Examples:

Input: str = “IITBBS”

Output: No

Input: str = “madam”

Output: Yes

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* stack;
int top = -1;

// push function
void push(char ele) {
stack[++top] = ele;
}

// pop function
char pop() {
return stack[top--];
}

// Function that returns 1

// if str is a palindrome
int isPalindrome(char str[]) {
int length = strlen(str);

// Allocating the memory for the stack

stack = (char*)malloc(length * sizeof(char));

// Finding the mid

int i, mid = length / 2;

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

push(str[i]);
}

// Checking if the length of the string

// is odd, if odd then neglect the
// middle character
if (length % 2 != 0) {
i++;
}

// While not the end of the string

while (str[i] != '\0') {
char ele = pop();
 // If the characters differ then the
// given string is not a palindrome
if (ele != str[i])
return 0;
i++;
}
return 1;
}

// Driver code
int main() {
char str[] = "madam";
if (isPalindrome(str)) {
printf("Yes");
} else {
printf("No");
}
return 0;
}

6. Write a C program to implement two stacks in a single array and

perform push and pop operations for both stacks.

#include <stdio.h>
#define MAX_SIZE 100

int stack[MAX_SIZE];
int top1 = -1;
int top2 = MAX_SIZE;

void push1(int data) {

if (top1 == top2 - 1) {
printf("Overflow stack!\n");
return;
}
top1++;
 stack[top1] = data;
}

int pop1() {
if (top1 == -1) {
printf("Empty Stack!\n");
return -1;
}
int data = stack[top1];
top1--;
return data;
}

void push2(int data) {

if (top2 == top1 + 1) {
printf("Overflow stack!\n");
return;
}
top2--;
stack[top2] = data;
}

int pop2() {
if (top2 == MAX_SIZE) {
printf("Empty Stack!\n");
return -1;
}
int data = stack[top2];
top2++;
return data;
}

int main() {
//Input data in stack-1
push1(10);
push1(30);
push1(40);
 push1(50);
//Input data in stack-2
push2(20);
push2(40);
push2(50);
push2(60);
push2(70);

printf("Elements in Stack-1 are: ");

while (top1 != -1) {
printf("%d ", pop1());
}
printf("\n");

printf("Elements in Stack-2 are: ");

while (top2 != MAX_SIZE) {
printf("%d ", pop2());
}
printf("\n");
return 0;
}

7. Write a C Program for Evaluation of Postfix Expressions Using Stack.

#include <stdio.h>
#include <ctype.h>

#define MAXSTACK 100 /* for max size of stack */

#define POSTFIXSIZE 100 /* define max number of charcters in postfix
expression */

int stack[MAXSTACK];
int top = -1;

/* define push operation */

void push(int item) {
if (top >= MAXSTACK - 1) {
 printf("stack over flow");
return;
}
else {
top = top + 1;
stack[top] = item;
}
}

/* define pop operation */

int pop() {
int item;
if (top < 0) {
printf("stack under flow");
}
else {
item = stack[top];
top = top - 1;
return item;
}
}

/* define function that is used to input postfix expression and to evaluate it

*/
void EvalPostfix(char postfix[]) {
int i;
char ch;
int val;
int A, B;

/* evaluate postfix expression */

for (i = 0; postfix[i] != ')'; i++) {
ch = postfix[i];
if (isdigit(ch)) {
/* we saw an operand,push the digit onto stack
ch - '0' is used for getting digit rather than ASCII code of digit */
push(ch - '0');
 }
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
A = pop();
B = pop();

switch (ch) {
case '*':
val = B * A;
break;

case '/':
val = B / A;
break;

case '+':
val = B + A;
break;

case '-':
val = B - A;
break;
}

/* push the value obtained above onto the stack */

push(val);
}
}
printf(" \n Result of expression evaluation : %d \n", pop());
}

int main() {
int i;

/* declare character array to store postfix expression */

char postfix[POSTFIXSIZE];
printf("ASSUMPTION: There are only four operators(*, /, +, -) in an
expression and operand is single digit only.\n");
 printf(" \nEnter postfix expression,\npress right parenthesis ')' for end
expression : ");

/* take input of postfix expression from user */

for (i = 0; i <= POSTFIXSIZE - 1; i++) {
scanf("%c", &postfix[i]);

if (postfix[i] == ')') {
break;
}
}

/* call function to evaluate postfix expression */

EvalPostfix(postfix);
return 0;
}

8. Write a C program to convert Infix expression to postfix expression

using stack.

// C code to convert infix to postfix expression

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_EXPR_SIZE 100

// Function to return precedence of operators

int precedence(char operator)
{
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
 return 2;
case '^':
return 3;
default:
return -1;
}
}

// Function to check if the scanned character

// is an operator
int isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/'
|| ch == '^');
}

// Main function to convert infix expression

// to postfix expression
char* infixToPostfix(char* infix)
{
int i, j;
int len = strlen(infix);
char* postfix = (char*)malloc(sizeof(char) * (len + 2));
char stack[MAX_EXPR_SIZE];
int top = -1;

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

if (infix[i] == ' ' || infix[i] == '\t')
continue;

// If the scanned character is operand

// add it to the postfix expression
if (isalnum(infix[i])) {
postfix[j++] = infix[i];
}

// if the scanned character is '('

 // push it in the stack
else if (infix[i] == '(') {
stack[++top] = infix[i];
}

// if the scanned character is ')'

// pop the stack and add it to the
// output string until empty or '(' found
else if (infix[i] == ')') {
while (top > -1 && stack[top] != '(')
postfix[j++] = stack[top--];
if (top > -1 && stack[top] != '(')
return "Invalid Expression";
else
top--;
}

// If the scanned character is an operator

// push it in the stack
else if (isOperator(infix[i])) {
while (top > -1
&& precedence(stack[top])
>= precedence(infix[i]))
postfix[j++] = stack[top--];
stack[++top] = infix[i];
}
}

// Pop all remaining elements from the stack

while (top > -1) {
if (stack[top] == '(') {
return "Invalid Expression";
}
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
return postfix;
}

// Driver code
int main()
{
char infix[MAX_EXPR_SIZE] = "a+b*(c^d-e)^(f+g*h)-i";

// Function call
char* postfix = infixToPostfix(infix);
printf("%s\n", postfix);
free(postfix);
return 0;
}