GenericStack.java from the boook Balanced Parentheses, Curly Braces, and Square
ID: 3908723 • Letter: G
Question
GenericStack.java from the boook
Balanced Parentheses, Curly Braces, and Square Brackets A sequence of characters contains "balanced" parentheses if the left- and right-parenthesis characters contribute to the formation of valid mathematical expressions, such as (x+ (y/z)) *2. The JAVA language requires this, and any valid JAVA compiler enforces it. Other delimiters, such as curly bacesand square brackets 1 are also required to be balanced in a valid JAVA program In this project, we write a program that uses a stack of objects to checks if a text file is "balanced" with respect to three types of delimiters: parentheses, curly braces, and square brackets. The user enters a file name, and the program performs the following steps Read the contents of the file into an ArrayList of String objects. (Each line of the text file becomes one member of the ArrayList.) . Scan the ArrayList for delimiter characters: curly braces parentheses (). and brackets [I Whenever a left delimiter is found, create an object of the Occurrence class (described later in this document) and push it onto a stack of Occurrence objects. Whenever a right delimiter is found, the program must determine if it is correct or if it represents a "balanceer. Rules for Balancing Left and Right Delimiters The rules for balancing the delimiters are: . Each left delimiter is matched with a subsequent right delimiter of the same type 2. Each right delimiter is matched with a preceding left delimiter of the same type 3. If there are multiple pairs of delimiters, then the resulting blocks of text must be either totally disjoint (not overlapping), or one block of text is completely nested within the other The table below lists several examples. (Notice that the left- and right-delimiters are not necessarily on the same line of text.) Example Balanced or Remark Not Balanced abc (ee) gg Balanced The parentheses sequence and the square brackets sequence are disjoint abc (Id ef]ghi) I [ 123 [xy (they do not overlap). The square brackets sequence is nested within the parentheses sequence The square brackets sequence is nested within the curly braces sequence. The square brackets sequence overlaps the curly braces sequence. The left- and right-parenthesis characters are in the wrong order Balanced Balanced Not Balanced Not BalancedExplanation / Answer
Hello, looks like I have answered the same question before. Here is the completed code for this problem including ‘unresolved occurrence’ using given stack. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
EDIT: I’m getting troubles submitting the answer without losing the format. Showing character limit exceeded error. So I have to paste it as a plain text, which will cause the loss of code formatting and indentations. Sorry for the trouble. If you are using eclipse ,copy the code and press ctrl+shift+F to format the code
// BalanceCheck.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class BalanceCheck {
// list to represent lines of words from input file
static ArrayList<String> inputText;
/**
* method to check if the string contained in inputtext list is balanced or
* not
*/
static void check() {
/**
* Defining a generic stack
*/
GenericStack<Occurrence> stack = new GenericStack<Occurrence>();
int errorCount = 0;
/**
* looping through all lines
*/
for (int i = 0; i < inputText.size(); i++) {
String line = inputText.get(i);
/**
* looping through all characters in the line
*/
for (int j = 0; j < line.length(); j++) {
char c = line.charAt(j);
/**
* pushing to the stack if character is any type of opening
* brace
*/
if (c == '(') {
Occurrence occ = new Occurrence('(', ')', i + 1, j);
stack.push(occ);
}
if (c == '{') {
Occurrence occ = new Occurrence('{', '}', i + 1, j);
stack.push(occ);
}
if (c == '[') {
Occurrence occ = new Occurrence('[', ']', i + 1, j);
stack.push(occ);
}
// in case of closing braces, checking the top element of stack
if (c == ')' || c == '}' || c == ']') {
if (stack.isEmpty()) {
/**
* mismatch, no opening brace found
*/
System.out
.println("MISMATCH: No matching opening character found for '"
+ c
+ "' at line "
+ (i + 1)
+ " position: " + j);
errorCount++;
} else if (c == stack.peek().getExpectedRightValue()) {
/**
* match found at the top of the stack
*/
Occurrence occ = stack.peek();
System.out.println("MATCH: '" + c + "' at line "
+ (i + 1) + " balances " + occ.getLeftValue()
+ " at line " + occ.getLine() + ", position "
+ occ.getPosition());
stack.pop();
} else {
/**
* mismatch, different expected left value at the top of
* the stack
*/
Occurrence occ = stack.peek();
System.out.println("MISMATCH: '" + c + "' at line "
+ (i + 1) + " does NOT balance "
+ occ.getLeftValue() + " at line "
+ occ.getLine() + ", position "
+ occ.getPosition());
errorCount++;
}
}
}
}
/**
* checking for unresolved entries. (the remaining entries in stack)
*/
while (!stack.isEmpty()) {
// getting top element from stack
Occurrence occ = stack.peek();
// displaying it
System.out.println("Unresolved Occurrence: line " + occ.getLine()
+ ", position: " + occ.getPosition() + ": "
+ occ.getLeftValue() + " " + occ.getExpectedRightValue());
// removing it
stack.pop();
}
System.out.println(errorCount + " error(s) found`");
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String fileName;
/**
* looping infinitely
*/
do {
/**
* getting file name
*/
System.out.println("Enter file name: (or 'q' to exit) ");
/**
* clearing the array list of words
*/
inputText = new ArrayList<String>();
/**
* getting file name
*/
fileName = scanner.nextLine();
if (!fileName.equalsIgnoreCase("q")) {
try {
/**
* opening the file, copying all lines to the array list
*/
Scanner fileScanner = new Scanner(new File(fileName));
while (fileScanner.hasNext()) {
String line = fileScanner.nextLine();
inputText.add(line);
}
/**
* displaying the file
*/
for (int i = 0; i < inputText.size(); i++) {
System.out.println((i + 1) + ": " + inputText.get(i));
}
/**
* performing balance check
*/
check();
} catch (FileNotFoundException e) {
// input file not found
e.printStackTrace();
}
}
} while (!fileName.equalsIgnoreCase("q"));
}
}
// Occurrence.java
public class Occurrence {
// attributes
private char leftValue;
private char expectedRightValue;
private int line;
private int position;
/**
* constructor
*
* @param leftValue
* - either (, { or [
* @param expectedRightValue
* - ) for (, } for { and ] for [
* @param line- line number
* @param position- position on the line
*/
public Occurrence(char leftValue, char expectedRightValue, int line,
int position) {
this.leftValue = leftValue;
this.expectedRightValue = expectedRightValue;
this.line = line;
this.position = position;
}
//getters
public char getLeftValue() {
return leftValue;
}
public char getExpectedRightValue() {
return expectedRightValue;
}
public int getLine() {
return line;
}
public int getPosition() {
return position;
}
}
/*OUTPUT*/
Enter file name: (or 'q' to exit)
input.txt
1: x = (a + b)
2: (
3: )
4: {
5: [(
6: )]
7: }
MATCH: ')' at line 1 balances ( at line 1, position 4
MATCH: ')' at line 3 balances ( at line 2, position 0
MATCH: ')' at line 6 balances ( at line 5, position 1
MATCH: ']' at line 6 balances [ at line 5, position 0
MATCH: '}' at line 7 balances { at line 4, position 0
0 error(s) found`
Enter file name: (or 'q' to exit)
input3.txt
1: x = (a + b)
2:
3: (
4:
5: )
6: {
7: [(
8: )
MATCH: ')' at line 1 balances ( at line 1, position 4
MATCH: ')' at line 5 balances ( at line 3, position 0
MATCH: ')' at line 8 balances ( at line 7, position 1
Unresolved Occurrence: line 7, position: 0: [ ]
Unresolved Occurrence: line 6, position: 0: { }
0 error(s) found`
Enter file name: (or 'q' to exit)
q
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.