Please ensure to test for all test cases. Remarks: Please do your best for the f
ID: 3726021 • Letter: P
Question
Please ensure to test for all test cases.
Remarks: Please do your best for the following questions. Please read the problems carefully and thoroughly before coding. If you have any questions about the problems, please use comments at the beginning of your program to write down your concerns. For each of the following problems, please use program. comments to record the time you spent on each of them at the beginning of your Problem 1: Parentheses Match (10/30 cases) 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 t 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. tray from the top, Here are all matching group symbols:(0). 1. (0, and co. 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 (5+7) true 5 7 false ((5+7) 3) true 15+71*3> true 1(S+7)*13 true 5+7)3 true 5+(73 true 547)"3 false IS+7] 3 false I5+7)3) false +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 I public static final String LEFT public static final String RIGHT "l!s" public static void main(Stringl) argsH //add code to test your checkParen() method public static boolean checkParen(String s)f //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 4. To test your program, please run ParentMatchTester class by clicking the Run JUnit buttonExplanation / Answer
public class ParenMatch {
public static final String LEFT = "([{<";
public static final String RIGHT = ")]}>";
static class stack
{
int top=-1;
char items[] = new char[100];
void push(char x)
{
if (top == 99)
{
System.out.println("Stack full");
}
else
{
items[++top] = x;
}
}
char pop()
{
if (top == -1)
{
System.out.println("Underflow error");
return '';
}
else
{
char element = items[top];
top--;
return element;
}
}
boolean isEmpty()
{
return (top == -1) ? true : false;
}
}
public static boolean isMatchingPair(char char1, char char2)
{
if(LEFT.indexOf(char1) == RIGHT.indexOf(char2))
return true;
else
return false;
}
/* Return true if expression has balanced
Parenthesis */
public static boolean checkParen(String s)
{
/* Declare an empty character stack */
stack st=new stack();
/* Traverse the given expression to
check matching parenthesis */
for(int i=0;i<s.length();i++)
{
/*If the exp[i] is a starting
parenthesis then push it*/
char x = s.charAt(i);
if (LEFT.indexOf(x)!=-1)
st.push(x);
/* If exp[i] is an ending parenthesis
then pop from stack and check if the
popped parenthesis is a matching pair*/
if (RIGHT.indexOf(x)!=-1)
{
/* If we see an ending parenthesis without
a pair then return false*/
if (st.isEmpty())
{
return false;
}
/* Pop the top element from stack, if
it is not a pair parenthesis of character
then there is a mismatch. This happens for
expressions like {(}) */
else if ( !isMatchingPair(st.pop(), x) )
{
return false;
}
}
}
/* If there is something left in expression
then there is a starting parenthesis without
a closing parenthesis */
if (st.isEmpty())
return true;
else
{
return false;
}
}
public static void main(String args[]) {
String test[] = {"5+7","(5+7)",")5+7(","((5+7)*3)","<{5+7}*3>","[(5+7)*]3","(5+7)*3","5+(7*3)","[(5+7)*3","[{5+7]*3}","[{5+7)*3])","([{5+7)*3]"};
for(int i=0;i<test.length;i++){
System.out.println(test[i] +" "+checkParen(test[i]));
}
}
}