A fairly common algorithmic task is to process some data set in reverse order. T
ID: 3726191 • Letter: A
Question
A fairly common algorithmic task is to process some data set in reverse order. Typically you put some data in temporary storage, then take it out, always in a Last-In, First-Out (LIFO) order. A stack is the data structure that was invented to help manage this process. A real-world example of a stack is the dispenser of the trays in the lunch room. You always take the top tray from the top, never from the middle or the bottom. Similarly, the lunch workers always put trays on the top, never at the middle or bottom. For this problem, you are going to determine whether the grouping symbols--parentheses, brackets, curly braces, etc.--in an arithmetic expression, such as [(5+7)*3], match each other. Here are all matching group symbols: (), [], {}, and <>. For this problem, you can ignore all digits and operands. Study the following cases to examine how matching symbols are evaluated. Parentheses Match 5+7 true (5+7) true )5+7( false ((5+7)*3) true <{5+7}*3> true [(5+7)*]3 true (5+7)*3 true 5+(7*3) true ((5+7)*3 false [(5+7]*3) false [(5+7)*3]) false ([(5+7)*3] false For this problem, please perform the following tasks: 1. Create a class named ParenMatch.java, then copy and paste the following code: public class ParenMatch { public static final String LEFT = "([{<"; public static final String RIGHT = ")]}>"; public static void main(String[] args){ //add code to test your checkParen() method } public static boolean checkParen(String s){ //implement this method to return true if grouping symbols match //each other, otherwise return false. } } 2. Implement checkParen method. You may want to design a Stack class, and use a stack to implement the checkParen method. You can design as many classes and methods as needed. But only checkParen(String s) method will be tested and graded. 3. You may want to add code in the main method to test your checkParen method
Explanation / Answer
import java.util.EmptyStackException;
import java.util.Stack;
/** Class to check for balanced parentheses.
* @author Pravesh
**/
public class ParenMatch {
// Constants
/** Set of opening parenthesis characters. */
private static final String LEFT = "([{<";
/** Set of closing parenthesis characters, matches LEFT. */
private static final String RIGHT = ")]}>";
public static boolean checkParen(String expression) {
// Create an empty stack.
Stack<Character> s = new Stack<Character>();
boolean balanced = true;
try {
int index = 0;
while (index < expression.length()) {
char nextCh = expression.charAt(index);
if (isOpen(nextCh)) {
s.push(nextCh);
} else if (isClose(nextCh)) {
char topCh = (char) s.pop();
balanced =LEFT.indexOf(topCh) == RIGHT.indexOf(nextCh);
if(!balanced){
System.out.println("mismatch is "+topCh+" and "+nextCh);
return false;
}
}
index++;
}
} catch (EmptyStackException ex) {
System.out.println("Extra closing parenthesis");
return false;
}
if(!s.empty()){
System.out.println("extra opening paranthesis: "+s.toString());
return false;
}
return true;
}
/**
* Method to determine whether a character is one of the
* opening parentheses.
* @param ch Character to be tested
* @return true if ch is one of the opening parentheses
*/
private static boolean isOpen(char ch) {
return LEFT.indexOf(ch) > -1;
}
/**
* Method to determine whether a character is one of the
* closing parentheses.
* @param ch Character to be tested
* @return true if ch is one of the closing parentheses
*/
private static boolean isClose(char ch) {
return RIGHT.indexOf(ch) > -1;
}
public static void main(String[] args) {
String str = "{[public()]exmpty}";
if(checkParen(str))
System.out.println("Balanced");
else
System.out.println("Not Balanced");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.