1 Problem description Main objective: Determine whether any expression with mult
ID: 3604971 • Letter: 1
Question
1 Problem description Main objective: Determine whether any expression with multiple kinds of brackets, braces and parentheses is balanced using a reference-based stack. You must implement the stack directly yourselves. Using a stack library, or JCF stacks, or a list ADT will earn no credit. Types of brackets: There are four “parenthesis/bracket” pairs: • ( and ) • [ and ] • { and } • < and > A line may contain other characters (including spaces) besides these 8 characters, but those characters are ignored. An expression is balanced if all the “open parentheses” are closed by a matching “close parentheses”, and nested parenthesis match, so that (for example) you can have “]” closing “{“, or a stray extra “)“ when there isn’t an open “(“. 2 For example, the following lines are all not valid (N): ab(x]w alpha{ beta (([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog ) < { } > html < And the following lines are all valid (Y): ab[x]w alpha{ betadelta} ([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog metamorphosis < html > ( [ < { } > ] ) < < ( ) > > You will not get any credit if you do not implement your solution to HW3 using a reference-based stack. Furthermore, you have to write your own stack from scratch. You cannot use any built-in libraries for stacks or linked lists, nor can you use an ADT for lists or an array-based stack. Format: You should provide a Makefile. Running make should create “Balanced.jar”. Your program should take two command line arguments, an input file and an output file. Input The input file consists of a series of lines as described above, each (including the last line) ending with an end-of-line. Output: On running (say) : java -jar Balanced.jar my-input.txt my-output.txt the file my-input.txt is read in and the file my-output.txt should be output. The i’th line of the output file my-output.txt corresponds to the i’th line in the input file my-input.txt. The i’th line of the output file should contain just :a single character, as follows: • If the i’th line is not valid, then the i’th line should just be “N” (without the quotes). • If the i’th line is valid, then the he i’th line should just be “Y” (without the quotes). 3 Examples: Piazza has a zip file for HW3 called HW3files.zip. The files test-input.txt and test-output.txt (which should help you see if your program is correct) are for the checker. Two additional files, more-input.txt and more-output.txt that are in the zip file will also help you test your program.
Explanation / Answer
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
/*user defined stack directory to perform the stack
operations*/
class MyCustomStack<E>
{
//private variables
private final int stackSize;
private int topOfStack;
private E[] entries;
//class constructor
public MyCustomStack()
{
this(10);
}
//paremetrized constructor
public MyCustomStack(int len)
{
stackSize=len>0?len:10;
topOfStack=-1;
entries=(E[])new Object[stackSize];
}
//method to push entries
public void push(E inElement)
{
if(topOfStack==stackSize-1)
System.out.println("Overflow");
entries[++topOfStack]=inElement;
}
//method to pop entries
public E pop()
{
if(topOfStack==-1)
System.out.println("Underflow");
return entries[topOfStack--];
}
//method to check the empty status
public boolean isEmpty()
{
//return the empty status
return (topOfStack==-1);
}
}
//main class to perform the parenthesis check
public class ParenMatch {
//define the parenthesis/bracket” pairs
private static final char left_Parent = '(';
private static final char right_Parent = ')';
private static final char left_bra = '{';
private static final char right_bra = '}';
private static final char left_squ = '[';
private static final char right_squ = ']';
private static final char right_cone = '>';
private static final char left_cone = '<';
//method to check the balanced status
public static boolean isPBBalanced(String testString) {
//create the stack instance
MyCustomStack<Character> muStackObj = new MyCustomStack<Character>();
StringBuilder tempString = new StringBuilder();
//The for loop to perform the check
for (int itr = 0; itr < testString.length(); itr++) {
tempString.append(testString.charAt(itr));
if (testString.charAt(itr) == left_Parent) {
muStackObj.push(left_Parent);
}
else if (testString.charAt(itr) == left_bra) {
muStackObj.push(left_bra);
}
else if (testString.charAt(itr) == left_squ) {
muStackObj.push(left_squ);
}
else if (testString.charAt(itr) == left_cone) {
muStackObj.push(left_cone);
}
else if (testString.charAt(itr) == right_Parent) {
if (muStackObj.isEmpty()) {
return false;
}
if (muStackObj.pop() != left_Parent) {
return false;
}
}
else if (testString.charAt(itr) == right_bra) {
if (muStackObj.isEmpty()) {
return false;
}
if (muStackObj.pop() != left_bra) {
return false;
}
}
else if (testString.charAt(itr) == right_squ) {
if (muStackObj.isEmpty()) {
return false;
}
if (muStackObj.pop() != left_squ) {
return false;
}
}
else if (testString.charAt(itr) == right_cone) {
if (muStackObj.isEmpty()) {
return false;
}
if (muStackObj.pop() != left_cone) {
return false;
}
}
}
//if string succesfully processed
boolean isPBBalanced = muStackObj.isEmpty();
//return true
return isPBBalanced;
}
public static void main(String[] args) throws FileNotFoundException, IOException {
FileWriter writObj = null;
BufferedWriter buffWrit = null;
if(args.length<2)
{
System.out.println("Command line arguments Error");
System.out.println("Please pass the files as command line arguments");
}
else
{
//open the files, passed as arguments
File file = new File(args[0]);
writObj = new FileWriter(args[1]);
buffWrit = new BufferedWriter(writObj);
FileReader fileReader = new FileReader(file);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String testLine;
//The while loop to process each line
while ((testLine = bufferedReader.readLine()) != null) {
//if line is balaced
if(isPBBalanced(testLine))
{
buffWrit.write("Y");
buffWrit.newLine();
}
//if line is not balaced
else
{
buffWrit.write("N");
buffWrit.newLine();
}
}
//close the objects
buffWrit.close();
fileReader.close();
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.