A valid expression is one where the number of opening parenthesis is equal to th
ID: 3862754 • Letter: A
Question
A valid expression is one where the number of opening parenthesis is equal to the number of closing ones, for each type of parenthesis. But also, when we encounter a closing parenthesis, it has to be the same type as the last opening parenthesis that wasn’t treated. For instance, “ (4 + [2 - 1)] " is not valid! You need to implement an algorithm using a stack to validate expressions: return true if the expression is valid, false otherwise. Also, the analysis should go through the stack only once. You will need to create your implementation in the class Balanced, name this method algo2. (the model solution is about 15 lines!) Do several tests using valid and invalid expressions. Make sure that your algorithm treats this case: "((())". How do you deal with this case?
Balanced.java
Explanation / Answer
Below is the working program and sample output at the end:
import java.util.Stack;
public class Balanced {
public static boolean algo1(String s) {
int curly = 0;
int square = 0;
int round = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case '{':
curly++;
break;
case '}':
curly--;
break;
case '[':
square++;
break;
case ']':
square--;
break;
case '(':
round++;
break;
case ')':
round--;
}
}
return curly == 0 && square == 0 && round == 0;
}
/**
* Algo 2
*
* @param s
* @return
*/
public static boolean algo2(String s) {
// Use of stack
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// push the starting brackets on to stack. push() - Pushes an item
// onto the top of this stack
if (c == '{' || c == '[' || c == '(') {
stack.push(c);
}
// Whenever a closing paranthesis of ')' type is met in the,
// do not
// add this onto stack, and remove the starting paranthesis of same
// type i.e.
// '('. This is exactly taking care of FACT 1: "when we encounter a
// closing parenthesis, it has to be the same type as the last
// opening parenthesis".
// pop - Removes the object at the top of this stack and returns
// that object as the value of this function.
if (c == ')') {
if (!(stack.pop() == '(')) {
// Whenver opening and closing paranthesis are of not same
// type return false as expression is not valid cause of
// contradiction with FACT 1 mentioned in above comment.
return false;
}
}
// Whenever a closing paranthesis of '}' type is met in the, do not
// add this onto stack, and remove the starting paranthesis of type
// '{'. This is exactly taking care of fact "when we encounter a
// closing parenthesis, it has to be the same type as the last
// opening parenthesis"
if (c == '}') {
if (!(stack.pop() == '{')) {
return false;
}
}
// Whenever a closing paranthesis of '}' type is met in the, do not
// add this onto stack, and remove the starting paranthesis of type
// '{'. This is exactly taking care of fact "when we encounter a
// closing parenthesis, it has to be the same type as the last
// opening parenthesis"
if (c == ']') {
if (!(stack.pop() == '[')) {
return false;
}
}
}
// If stack is not empty it is not a valid expression cause of the FACT
// 2: "number of opening parenthesis is equal to the number of closing
// ones, for each type of parenthesis". If something is left on stack it
// means paranthesis were not in pair.
return stack.isEmpty();
}
public static void main(String[] args) {
for (int i = 0; i < args.length; i++) {
System.out.println("algo1( "" + args[i] + "" ) -> " + algo1(args[i]));
System.out.println("algo2( "" + args[i] + "" ) -> " + algo2(args[i]));
}
}
}
--------------------------------
// Output
algo1( "{45+(56+[9*3])}" ) -> true
algo2( "{45+(56+[9*3])}" ) -> true
algo1( "((())" ) -> false
algo2( "((())" ) -> false
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.