1 Define a Stack ADT named CharStackjava and use a linkedLis

1) Define a Stack ADT named CharStack.java, and use a linkedList to implement the ADT. The Stack ADT should have only one data member: LLNode top; (LLNode is provided).

2) Design a tester program named ParenthesesMatch.java, within this class, define a static method as specified in the following header to evaluate if a String has matching parentheses. If they don\'t match, return false. Somehow, determine the end of this process and return true if the expression has passed all the matches. public static boolean checkParentheses(String s) The String to be tested is passed to the program though command argument list

Here is the LLNode class and tester output example:

public class LLNode{

private LLNode link;
private char data;

public LLNode(LLNode link, char data){
setLink(link);
setData(data);
}

public LLNode getLink(){
return link;
}
public char getData(){
return data;
}
public void setLink(LLNode link){
this.link = link;
}
public void setData(char data){
this.data = data;
}
}

Tester Output:

Parentheses Match

5+7 good!

(5+7) good!

)5+7( BAD

((5+7)*3) good!

<{5+7}*3> good!

[(5+7)*]3 good!

(5+7)*3 good!

5+(7*3) good!

((5+7)*3 BAD

[(5+7]*3) BAD

[(5+7)*3]) BAD

([(5+7)*3] BAD

Solution

Class CharStack.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LLNode<Item> implements Iterable<Item> {

    private String n; //Name of string
    private Node start;
    private Node tail = start;

    //Constructor name
    public LinkedList(String name) {
        this.name = name;
        head = null;
        tail = head;
    }

    //The nodes in the list
    private class Node {

        Item str;    // Data of list   
    Node n;        //Next element
        Node p;        // Previous element

        //Node constructor
        public Node(Item istr) {
            Item str;
            n = null;
            p = null;
        }

     public String toString() {
            return data.toString();
        }
    }

   
    // Adding element node to end of list, push
    public void push(Item newstr) {
        if (isEmpty()) {          //If it\'s the first element of the list
            head = new Node(newstr);
            tail = head;
        } else {
            tail.next = new Node(newstr);
            tail.n.p = tail;
            tail = tail.n;
        }
    }

  
   public Item pop() {
        if (isEmpty()) throw new NoSuchElementException(\"List empty\"); // remove when there\'s no nodes left

        Item toReturn = tail.str;

        if(tail != head) { //If there\'s more then one node left
            tail = tail.p;
            tail.n = null;
        } else { //Remove the last node
            tail = head = null;
        }

        return toReturn;
    }

    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException(\"underflow of stack\");
        return LLNode.item;
    }
    private boolean empty() {
        return head == null;
    }
  
//Method for checking parentheses

public static boolean checkParentheses(String str) {
    LLNode<Character> lnode = new LLNode<Character>();

    char c;
    for(int i=0; i < str.length(); i++) {
        c = str.charAt(i);

       if(c == \'(\')
            lnode.push(c);
        else if(c == \'{\')
            lnode.push(c);
        else if(c == \')\')
            if(lnode.empty())
                return false;
            else if(lnode.peek() == \'(\')
                lnode.pop();
            else
                return false;
        else if(c == \'}\')
            if(lnode.empty())
                return false;
            else if(lnode.peek() == \'{\')
                lnode.pop();
            else
                return false;

        }
        return lnode.empty();
}

public static void main(String[] args) {      
    String str = \"({})\";
    System.out.println(Weekly12.checkParentheses(str));
}

}