Scribd
Upload
36 views

Data Structure Assignment 1

The document contains code for two programs - Program 1 checks if brackets in a string are balanced by using a stack, and Program 2 implements a stack using a linked list. Program 1 defines a Stack class with push, pop and other methods, and also functions to check for open/close brackets. It then runs checkInput on different test strings. Program 2 defines a Node class and StackusingLinkList class with push, pop and top methods to implement a stack using linked list. It tests the stack on different inputs.

Uploaded by

Muhammad Asad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
36 views

Data Structure Assignment 1

The document contains code for two programs - Program 1 checks if brackets in a string are balanced by using a stack, and Program 2 implements a stack using a linked list. Program 1 defines a Stack class with push, pop and other methods, and also functions to check for open/close brackets. It then runs checkInput on different test strings. Program 2 defines a Node class and StackusingLinkList class with push, pop and top methods to implement a stack using linked list. It tests the stack on different inputs.

Uploaded by

Muhammad Asad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Name: Fazeel Ahmed Khan

Class: BS Software (Part II)

Roll No: 2k19/SWE/35

Subject: Data Structure & Algorithms

Submitted to: Dr. Niaz Arijo

Date: 16-7-2020
Assignment 1

Program 1

public class A1{

class Stack{
char data[];
int totalItems;
int totalSize;
Stack(int size){
data = new char[size];
totalSize = size;
totalItems = 0;
}

void push(char item){


System.out.println("pushing "+item);
data[totalItems++] = item;
}
char pop(){
System.out.println("poping "+data[totalItems-1]+"index
"+totalItems);
return data[--totalItems];
}
boolean isFull(){
return totalSize == totalItems;
}
boolean isEmpty(){
return totalItems == 0;
}
int size(){
return totalSize;
}
}

boolean isOpenBracket(char ch){


return ch == '('|| ch == '{' || ch == '[';
}
boolean isCloseBracket(char ch){
return ch == ')' || ch == '}' || ch == ']';
}

boolean matchBrackets(char c1 , char c2){


System.out.println("matching "+c1+" "+c2);
if(c1 == '(' && c2 == ')')
return true;
else if(c1 == '{' && c2 == '}')
return true;
else if(c1 == '[' && c2 == ']')
return true;
else return false;
}

void checkInput(String input){


Stack stack = new Stack(input.length());

for(int i = 0; i<input.length(); i++){


if(stack.isEmpty()){
if(isOpenBracket(input.charAt(i))){
stack.push(input.charAt(i));
}else if(isCloseBracket(input.charAt(i))){
System.out.println("Error: The code
|"+input.charAt(i)+"| dosen't use brackets correctly it start with closing
bracket");
return;
}
}else{
if(isCloseBracket(input.charAt(i))){

if(matchBrackets(stack.pop(),input.charAt(i))){
System.out.println("Success: Pair
Matched");
}else{
System.out.println("Error:
|"+input.charAt(i)+"| Pair doesn't matched");
return;
}
}else if(isOpenBracket(input.charAt(i))){
stack.push(input.charAt(i));
}
}
}
}

public static void main(String args[]){


System.out.println("Testing Input 1");
new A1().checkInput("()");
System.out.println("Testing Input 2");
new A1().checkInput("({})");
System.out.println("Testing Input 3");
new A1().checkInput("{}[]");
System.out.println("Testing Input 4");
new A1().checkInput("(())");
System.out.println("Testing Input 5");
new A1().checkInput("{[]}()");
System.out.println("Testing Input 6");
new A1().checkInput("}");
System.out.println("Testing Input 7");
new A1().checkInput("foo(bar[i])");
}
}

Program 2

public class StackusingLinkList{

class Node{
Object data;
Node next;
Node(Object _data){
this.data = _data;
}

public void setData(Object _data){


this.data = _data;
}
public Object getData(){
return this.data;
}
}

private Node top;

StackusingLinkList(){
this.top = null;
}

public void push(Object value){


Node temp = new Node(value);

if(temp == null){
System.out.println("Why this!");
return;
}
temp.next = top;
top = temp;
}

public boolean isEmpty(){


return top == null;
}
public Object pop(){
if(top == null){
System.out.println("There is no Data!");
return null;
}
Object p = top.getData();
top = top.next;
return p;
}

public Object top(){


if(!isEmpty()){
return top.data;
}else{
return null;
}
}

public static void main(String args[]){


StackusingLinkList stack = new StackusingLinkList();

System.out.println("Input 1");
stack.push(2);
stack.push(1);
System.out.println(stack.top());
System.out.println(stack.pop());
System.out.println("Input 2");
StackusingLinkList input2 = new StackusingLinkList();
input2.push(1);
input2.push(2);
System.out.println(input2.top()+"\n"+input2.pop());
System.out.println("Input 3");
StackusingLinkList input3 = new StackusingLinkList();
input3.push(2);
input3.push(3);
input3.push(9);
input3.push(7);
input3.push(2);
System.out.println(input3.top()+"\n"+input3.pop()+"\n"+input3.top
());

}
}

You might also like