Sunday, November 29, 2020

Finding whether a given string has balanced parenthesis using Java Stack

 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 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