Write a java program to detect unmatched/missing parentheses in source code file
ID: 673619 • Letter: W
Question
Write a java program to detect unmatched/missing parentheses in source code files. Use the stack ADT.
Part 1:
You will implement a simplified list interface. The list interface has been given to you in
ISimpleList.java. You will write a generic class SinglyLinkedList.java which implements the
ISimpleList interface. The class will be an implementation of this interface using a singly linked list.
public class SinglyLinkedList<T> implements ISimpleList<T> {
private class Node {
T val;
Node next;
}
private Node front;
private Node back;
private int size;
…
}
The only public methods your class should have are the methods of the interface it implements.
The methods should have a time performance.
Start with the simpler methods and do not move on to the next method unless you have tested
and are absolutely sure the method you just completed is 100% correct. Bugs are much harder to find
when they accumulate. Be careful of edge cases (e.g. adding to empty list, removing last element, etc)
It is okay to move to Part 2 before you have completed all the methods in Part 1 but make sure
you have implemented those needed for Part 2 and they are correct. You can come back to fill in the
rest later. You do not have to worry about the client calling methods which take an index with an out of
range index parameter. You can assume the client is well behaved.
The generic T is just a type (does not matter what) that will be specified by the client of the list.
You can pretend it is String while you're implementing the interface, if that helps your thinking. For
example:
ISimpleList<String> list = new SinglyLinkedList<String>();
list.add(“this is so easy!”);
Part 2:
You plan to use the SinglyLinkedList class you wrote as the basis of your implementation of
the stack ADT. The stack interface has been given to you in ISimpleStack.java. You will write a generic
class SimpleStack.java which implements the ISimpleStack interface.
public class SimpleStack<T> implements ISimpleStack<T> {
// Composition. It “Has-A” list.
...
}
The only public methods your class should have are the methods of the interface it implements.
All your operations should be O(1).
Hints:
If you find yourself writing more than 1 line of code for each of the methods you implement
you are likely doing something wrong.
You do not have to worry about the client calling peek() or pop() on an empty stack. You can
assume the client will always call isEmpty before to make sure it is not empty.
Part 3:
You will use the SimpleStack class you wrote to implement an algorithm that detects
unmatched parentheses. The class ParenthesesChecker.java which contains a single static method
checkParentheses has been given to you with some of the functionality in place. You can fill out the
missing code or you can implement the whole method yourself if you would rather not use the given
code. The method signature
public static boolean checkParentheses(String filename) {
must not be changed. Inside the method feel free to implement it any way you like using the stack from
part 2.
The method reads in a file like the sample files given. If it detects not well matched “(“ “)” it
returns false. If the parentheses are all matched, it returns true. Make sure you detect cases like below
as not well formed:
) (
) ( )
( ) )
( ) (
( ( )
Hint:
The algorithm is very simple:
Process the input tokens in order.
When you see a “(“ you push it to the stack.
When you see a “)” you:
– if the stack is empty you have detected a not well matched parenthesis. Return false.
– if the stack is not empty, you pop from the stack.
(All tokens other than “(“ and “)” are ignored.)
If the stack is not empty after you have processed all the input tokens, you have detected a not well
matched parenthesis. Return false.
If the stack is empty after you have processed all the input tokens, you return true.
These are the given codes:
********************************************************ISimpleList.java******************************************************
public interface ISimpleList<E> {
/**
*
* @return the list size
*/
int size();
/**
* Add item e to the end of the list
* @param e
*/
void add(E e);
/**
* Print all the elements of the list IN ONE LINE in between square brackets
* e.g.: [ item1, item2, item3, item4 ]
*
*/
void printList();
/**
* Get the element at position index
*
* @param index
* @return
*/
E get(int index);
/**
* Set the element at position index to the given element
* @param index
* @param element
*/
void set(int index, E element);
/**
* Add item e at position index
*
* @param index
* @param element
*/
void add(int index, E element);
/**
* Remove the item at position index and return the item that was just removed
*
* @param index
* @return The element which was removed
*/
E remove(int index);
}
******************************************************ISimpleStack.java**************************************************************
public interface ISimpleStack<E> {
/**
* True if the stack is empty, false otherwise
*
* @return
*/
boolean isEmpty();
/**
* Add item e to the stack
*
* @param e
*/
void push(E e);
/**
* Remove the element at the top of the stack and return it
* @return
*/
E pop();
/**
* Get the element at top of the stack
* @return
*/
E peek();
}
*************************************************************ParenthesesChecker.java*********************************************
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class ParenthesesChecker {
public static boolean checkParentheses(String filename) {
ISimpleStack<String> stack = new SimpleStack<String>();
String delimiters = " ()";
try (Scanner in = new Scanner(new File(filename))) {
while (in.hasNextLine()) {
StringTokenizer st = new StringTokenizer(in.nextLine(), delimiters, true);
while (st.hasMoreTokens()) {
String token = st.nextToken();
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return true;
}
// Please remove your main() function when you submit this file
// public static void main(String[] args) {
// System.out.println(checkParentheses("sample_wellFormed.txt"));
// }
}
*******************************************************************************************
Submit these completed codes:
SinglyLinkedList.java
SimpleStack.java
ParenthesisChecker.java
Explanation / Answer
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size ;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print(" Singly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}
/* Class SinglyLinkedList */
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
linkedList list = new linkedList();
System.out.println("Singly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Singly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
private int maxSize;
private long[] stackArray;
private int top;
public MyStack(int s) {
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
public void push(long j) {
stackArray[++top] = j;
}
public long pop() {
return stackArray[top--];
}
public long peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
MyStack theStack = new MyStack(10);
theStack.push(10);
theStack.push(20);
theStack.push(30);
theStack.push(40);
theStack.push(50);
while (!theStack.isEmpty()) {
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
}
System.out.println("");
}
}
2 question alternate code
import java.util.*;
public class StackDemo {
static void showpush(Stack st, int a) {
st.push(new Integer(a));
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
}
static void showpop(Stack st) {
System.out.print("pop -> ");
Integer a = (Integer) st.pop();
System.out.println(a);
System.out.println("stack: " + st);
}
public static void main(String args[]) {
Stack st = new Stack();
System.out.println("stack: " + st);
showpush(st, 42);
showpush(st, 66);
showpush(st, 99);
showpop(st);
showpop(st);
showpop(st);
try {
showpop(st);
} catch (EmptyStackException e) {
System.out.println("empty stack");
}
}
}
3.
public final class BalancedParanthesis {
private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
}
private BalancedParanthesis() {};
/**
* Returns true is parenthesis match open and close.
* Understands [], {}, () as the brackets
* It is clients responsibility to include only valid paranthesis as input.
* A false could indicate that either parenthesis did not match or input including chars other than valid paranthesis
*
* @param str the input brackets
* @return true if paranthesis match.
*/
public static boolean isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("String length should be greater than 0");
}
// odd number would always result in false
if ((str.length() % 2) != 0) {
return false;
}
final Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
assertEquals(true, isBalanced("{}([])"));
assertEquals(false,isBalanced("([}])"));
assertEquals(true, isBalanced("([])"));
assertEquals(true, isBalanced("()[]{}[][]"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.