Check if parentheses in string is properly nested or not! – JAVA

Question: Write the implementation of a method with:

input: a String output: true or false

true: if the String contains properly nested brackets

false: if they’re not properly nested

examples: for input=”([])” return should be true for input=”()” return should be true for input=”[(])” return should be false

Before I jump into writing the code, let’s think about any questions that would help us come up with better solution.

1. are we only considering () and [] and no other brackets? Assume only (), []

2. what data structure would we want to use here? Stack

3. Is keeping a counter for each occurrence good idea for this issue? probably not.

If you have any more questions, that I couldn’t think of, I would love to know. Please comment below.

Here’s pseudo algorithm:

1. Initiate stack

2. Look for char ( and [, if found push in stack

3. Look for char ) and ], if found, return false if stack empty or look for the first char in stack

4. If first char is the relative opening bracket{ ( OR [ }, pop, or return false.

5. Iterate this loop until stack is empty and end of string.

6. return state of stack is empty or not.

Here’s the code: 


import java.util.Stack;

public class Main {

public static void main(String[] args){

String validstr = "[Hello](world)([I am Don])";
String invalidstr = ")Hello()( world [i am] ]don[";
System.out.println(isValid(invalidstr));
}
public static boolean isValid(String input) {

Stack stack = new Stack();
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '['){
stack.push(input.charAt(i));
System.out.println("push" + stack);
}
else if (input.charAt(i) == ']') {
if (stack.empty())
return false;
else
if (stack.peek() == '[')
stack.pop();
else
return false;
}
else if (input.charAt(i) == '(') {
stack.push('(');
System.out.println("push" +stack);
}
else if (input.charAt(i) == ')') {
if (stack.empty())
return false;
else
if (stack.peek() == '(')
stack.pop();
else
return false;
}
else
continue;
}

return stack.empty();
}
}

Advertisements