CSC205AB Linked Stack

Steps

1. Download the following files onto your machine, into the default package:

• StackADT.java
• Node.java
• List.java
• Balance.java

2. Review the code so that you understand how it works.

• It will not compile or run until after step 3 below.

3. Create the Generic class LinkedStack which implements the interface StackADT.

• Use the Linked List implementation provided as your underlying datatype.

4. Run your program on the following test input strings:

• ( )
• ( () () )
• (this is (a test) (to see) ((if) (it)) (works))
• (()()
• (()))
• (if (expression) then (code code if (expression) then (code code)) code)
• Try this LISP function: (define fulladdr (lambda (a b x) (cons (l-xor (l-xor a b) x) (l-or (l-and x (l-or a b)) (l-and a ab)))))

Design

Model: see image.

Starter Codes

StackADT.java

public interface StackADT< T > {

public void push(T element);

public T pop();

public T peek();

public int size();

public boolean isEmpty();
}

Node.java

public class Node< T > {

private T data;
private Node< T > next;

public Node(T element, Node< T > next) {
data = element;
this.next = next;
}

public Node< T > getNext() {
return next;
}

public T getData() {
return data;
}

public void setNext(Node< T > n) {
next = n;
}
}

List.java

import java.util.NoSuchElementException;

public class List< T > {

private Node< T > head;

public List() {
head = null;
}

public int length() {
Node< T > n;
int i;

for (i = 0, n = head; n != null; n = n.getNext(), i++);

return i;
}

public void addFirst(T x) {
head = new Node< T >(x, head);
}

public void addLast(T x) {
if (head == null) {
head = new Node< T >(x, null);
} else {
Node< T > n;
for (n = head; n.getNext() != null; n = n.getNext());
n.setNext(new Node< T >(x, null));
}
}

public T getFirst() {
return head.getData();
}

public T get(int c) /* throws NoSuchElementException */ {
int target = c;
Node< T > n;
for (n = head; n.getNext() != null && target-- > 0; n = n.getNext());
if (target > 0) {
throw new NoSuchElementException("LinkedList.get: no element #" + c);
}
return n.getData();
}

public int find(String s) /* throws NoSuchElementException */ {
Node< T > n;
int i;
for (i = 0, n = head; n != null && n.getData().toString().compareTo(s) != 0; n = n.getNext(), i++);
if (n == null) {
throw new NoSuchElementException("LinkedList.find: no element " + s);
}
return i;
}

public void insertAfter(int c, T e) {
int target = c;
Node< T > n;
for (n = head; n.getNext() != null && target-- > 0; n = n.getNext());
if (target > 0) {
throw new NoSuchElementException("LinkedList.insertAfter: no element #" + c);
}
n.setNext(new Node< T >(e, n.getNext()));
}

public void insertAfter(String s, T e) {
Node< T > n;
for (n = head; n != null && n.getData().toString().compareTo(s) != 0; n = n.getNext());
if (n == null) {
throw new NoSuchElementException("LinkedList.insertAfter: no element " + s);
}
n.setNext(new Node< T >(e, n.getNext()));
}

public void delete(int c) {
int target = c;
Node< T > n;
if (c == 0) {
head = head.getNext();
} else {
for (n = head; n.getNext() != null && target-- > 1; n = n.getNext());
if (target > 1) {
throw new NoSuchElementException("LinkedList.delete: no element #" + c);
}
n.setNext(n.getNext().getNext());
}
}
}

Balance.java

import java.util.Scanner;

public class Balance {

private LinkedStack< Character > stack;

public static void main(String[] args) {
{
String expression, again;
boolean result;

Scanner in = new Scanner(System.in);

do {
Balance tester = new Balance();

System.out.println("Enter a string with ()'s: ");
expression = in.nextLine();

result = tester.isBalanced(expression);

System.out.println("\nThat expression " + (result ? "is balanced" : "is NOT balanced"));

System.out.print("Evaluate another expression [Y/N]? ");
again = in.nextLine();
System.out.println();
} while (again.equalsIgnoreCase("y"));

in.close();
}
}

public Balance() {
stack = new LinkedStack< Character >();
}

public boolean isBalanced(String s) {
char a = 'a';

for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
stack.push(a);
System.out.print(a++);
break;
case ')':
if (stack.size() == 0) {
return false;
}
System.out.print(stack.pop().charValue());
break;
default:
System.out.print(' ');
}
}
return stack.isEmpty();
}
}