Challenge: Given a string in the stdin with a set of parenthesis [{[()]}] and the stdout should print either true or false based on whether the parenthesis are matched or not
e.g:
{} --> true
{[()]} -->true
{[}] -- > false
Solution : I am going to use a Java Stack to resolve this problem following the below approach.
1.use stdin to read the input
2.iterate reading from stdin while there are more inputs
3.store each string in a variable and validate
4.validation >>
a. loop through each character of the string
b.If current character is ( OR { OR [ then add the value to the Stack
c.If the current character is ) OR } OR ] then pop a value from the Stack and compare it with the current character
d. if c matches then result is true , continue ; else set result as false
Below is the coding
-----------------------------------------------------------------------------------------------------------------------------
package com.hackerrank;
import java.util.Scanner;
import java.util.Stack;
public class Main {
/**
* Main method
* @param args
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); //stdin
while(scanner.hasNext()){ //reading continues till stdin has more inputs
String input = scanner.nextLine(); //read String
System.out.println(checkBalancedLine(input)); //validate and print result
}
}
/**
* This method validates the string with balanced paranthesis
* @param inputLine
* @return true or false
*/
public static boolean checkBalancedLine(String inputLine){
boolean balanced =false;
Stack<String> stringStack = new Stack<String>();
for(int i=0;i<inputLine.length();i++){
if((inputLine.charAt(i)=='(') || (inputLine.charAt(i)=='{') || (inputLine.charAt(i)=='[')) { //if the character is ([{ then add to the stack
stringStack.add(String.valueOf(inputLine.charAt(i)));
}
if((inputLine.charAt(i)==')') || (inputLine.charAt(i)=='}') || (inputLine.charAt(i)==']')) { //if the character is )]} then pop the stack and compare the ith value against the popped value
if(!stringStack.isEmpty()) {
String poppedString = stringStack.pop();
if (inputLine.charAt(i) == ')' && poppedString.equalsIgnoreCase("(")) {
balanced = true;
} else if (inputLine.charAt(i) == ']' && poppedString.equalsIgnoreCase("[")) {
balanced = true;
} else if (inputLine.charAt(i) == '}' && poppedString.equalsIgnoreCase("{")) {
balanced = true;
} else {
balanced = false;
}
}
}
}
return balanced;
}
}
Console
No comments:
Post a Comment