19ELC211 DSA

LABSHEET 2 & 3
SHREYA D PILLAI

AM.EN.U4ELC22040
1.
public class MyStack {
private int top;
private int[]arrstack;
private int capacity;
public MyStack(int
capacity)
{ this.capacity = capacity;
this.arrstack = new int[capacity];
this.top = -1;
} public boolean
isFull()
{ return top ==
capacity - 1;

} public boolean
isEmpty()
{ return top ==
top-1;
} public void push(int
element)
{
if (isFull()) {
System.out.println("Stack is full ");
return;
} arrstack[++top]
= element;
}
public void display()
{
for (int i = top;i>=0;i--)
{
System.out.println(arrstack[i]);
}
}
 public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return Integer.MIN_VALUE;
} int poppedElement =
arrstack[top--];
return
poppedElement;
}
public static void main(String[] args) {
MyStack stack = new MyStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.pop();
stack.pop();
stack.display();

}
}

Output:

2.
import java.util.Stack;
import java.util.Scanner;
class Q2
{
public static boolean isBalanced(String exp) {
Stack<Character> stack = new Stack<>();
for (char c : exp.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
 } else {
return false;
}
}
return
stack.isEmpty();
}
public static void main(String[] args) {
System.out.println("press 0 to exit");
Scanner sc=new Scanner(System.in);
while(true){
System.out.print("enter the parenthesis pairs: ");
String z=sc.nextLine(); if(z.equals("0")){
break;
}
else{
if (isBalanced(z)) {
System.out.println("Balanced");
} else {
System.out.println("Not Balanced");
}
}
}
sc.close();
}
}

Output:

3.
import java.util.Scanner;

class Stack {
private int top;
private int capacity;
private char[] array;

public Stack(int capacity) {

this.capacity = capacity;
this.array = new char[capacity];
this.top = -1;
}
 public boolean isFull() { return
this.top == this.capacity - 1;
} public boolean
isEmpty() { return
this.top == -1;
} public void push(char value) {
if (!this.isFull()) {
this.array[++this.top] = value;
}
} public char pop() { return this.isEmpty() ?
'\u0000' : this.array[this.top--]; } public static
String reverse(String str) { char[] charArr =
str.toCharArray(); int size = charArr.length;
Stack stack = new Stack(size);
for (int i = 0; i < size; ++i)
{ stack.push(charArr[i]);
}
for (int i = 0; i < size; ++i)
{ charArr[i] = stack.pop();
}
return
String.valueOf(charArr);
}
} public class
Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a string: ");
String str = scanner.nextLine();
scanner.close();

System.out.println("Reversed string: " + Stack.reverse(str));

}
}

Output:
4.
class CustomStack {
private int top;
private int capacity;
private int[] array;
public CustomStack(int capacity)
{ this.capacity = capacity;
this.array = new int[capacity];
this.top = -1;
} public boolean
isEmpty() { return
(top < 0);
} public boolean
isFull() {
return (top == capacity - 1);
} public void
push(int x) { if
(isFull()) {
System.out.println("Stack Overflow");
return;
}
array[++top] = x;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return array[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} return
array[top];
} public void
printStackFromBottomToTop() {
 if (isEmpty()) {
System.out.println("Stack is empty");
return;
}

CustomStack auxStack = new CustomStack(capacity);

while (!isEmpty()) {
int element = pop();
auxStack.push(element);
}
while (!auxStack.isEmpty()) {
int element = auxStack.pop();
System.out.print(element + " ");
push(element);
}
System.out.println();
}
} public class
Main1 {
public static void main(String[] args) {
CustomStack s = new CustomStack(4);
s.push(1);
s.push(2);
s.push(3);
s.push(4);

System.out.println("Elements from bottom to top:");

s.printStackFromBottomToTop();
}
}

Output:

5.

import java.util.Scanner;
class der { private
char[] stackArray;
private int top; private
int capacity;
public der(int capacity)
{
 this.capacity = capacity;
this.stackArray = new char[capacity];
this.top = -1;
} public boolean
isEmpty() { return
top == -1;
} public boolean isFull()
{ return top == capacity -
1;
} public void
push(char c) { if
(isFull()) {
System.out.println("Stack Overflow");
return;
}
stackArray[++top] = c;
} public char
pop() { if
(isEmpty()) {
System.out.println("Stack Underflow");
return '\u0000';
} return
stackArray[top--];
} public char
peek() { if
(isEmpty()) {
System.out.println("Stack is Empty");
return '\u0000';
}
return stackArray[top];
} public int
precedence(char c) {
switch (c) { case '+':
case '-':
return 1;
case '*': case
'/':
return 2;
case '^':
return 3;
default:
 return -1;
}
}
public String infixToPostfix(String infix) {
StringBuilder postfix = new StringBuilder();
for (char c : infix.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
postfix.append(c); } else if (c ==
'(') { push(c);
} else if (c == ')') {
while (!isEmpty() && peek() != '(') {
postfix.append(pop());
} pop(); } else {
while (!isEmpty() && precedence(c) <= precedence(peek())) {
postfix.append(pop());
}
push(c);
}
}
while (!isEmpty()) {
postfix.append(pop());
}
return
postfix.toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the Infix Expression: ");
String infixExpression = sc.nextLine();

der infixToPostfixConverter = new der(infixExpression.length());

String postfixExpression =
infixToPostfixConverter.infixToPostfix(infixExpression);
System.out.println("Postfix Expression: " + postfixExpression);
sc.close();
}
}

Output:
1.
public class DeleteMiddleElementInStack {
private int[] stackArray; private int
top; private int capacity;
public DeleteMiddleElementInStack(int capacity)
{ this.capacity = capacity;
this.stackArray = new int[capacity]; this.top
= -1;
} public boolean
isEmpty() { return top
== -1;
} public boolean isFull()
{ return top == capacity -
1;
} public void
push(int x) { if
(isFull()) {
System.out.println("Stack Overflow");
return;
}
stackArray[++top] = x;
} public int
pop() { if
(isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return stackArray[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} return
stackArray[top];
} public int
size() { return
top + 1;
}
 public void deleteMiddleElement()
{ int size = size();
int middle = size / 2;
int[] auxStack = new
int[size]; int auxTop = -1;
for (int i = 0; i < middle; i++)
{ auxStack[++auxTop] = pop();
}

pop();
while (auxTop >= 0)
{
push(auxStack[auxTop--]);
}
}
public static void main(String[] args) {
DeleteMiddleElementInStack stack = new
DeleteMiddleElementInStack(5); stack.push(1); stack.push(2);
stack.push(3); stack.push(4); stack.push(5);

System.out.println("Original Stack: " + stackToString(stack));

stack.deleteMiddleElement();

System.out.println("Stack after deleting middle element: " +

stackToString(stack));
}
private static String stackToString(DeleteMiddleElementInStack stack)
{ StringBuilder sb = new StringBuilder(); sb.append("[");
for (int i = stack.top; i >= 0; i--) {
sb.append(stack.stackArray[i]); if (i != 0) {
sb.append(", ");
} }
sb.append("]");
return sb.toString();
}
}

Output:
2.
import java.util.Stack;
public class PostfixEvaluator
{
public static void main(String[] args) {
String postfixExpression = "65*8+";
int result = evaluatePostfix(postfixExpression);
System.out.println("Postfix Expression: " + postfixExpression);
System.out.println("Result: " + result);
}
public static int evaluatePostfix(String postfixExpression) {
Stack<Integer> stack = new Stack<>();
for (char c : postfixExpression.toCharArray())
{ if (Character.isDigit(c)) {
stack.push(c - '0');
} else { int operand2 = stack.pop();
int operand1 = stack.pop(); int result =
performOperation(operand1, operand2, c);
stack.push(result);
}
}
return
stack.pop();
} public static int performOperation(int operand1, int
operand2, char operator) { switch (operator) {
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
if (operand2 != 0) {
return operand1 / operand2;
} else { throw new
ArithmeticException("Division by zero");
}
default:

throw new IllegalArgumentException("Invalid operator: " +

operator); }
 }
}
Output: