Last active
July 9, 2016 04:04
-
-
Save NakulRajan/d89f5110f4c6c3de08c6c1d1b011a49b to your computer and use it in GitHub Desktop.
Check whether Valid Parentheses
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import org.junit.Test; | |
| import java.util.HashMap; | |
| import java.util.Stack; | |
| import static org.junit.Assert.assertFalse; | |
| import static org.junit.Assert.assertTrue; | |
| /** | |
| * Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. | |
| * The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. | |
| */ | |
| public class ValidParentheses { | |
| private HashMap<Character, Character> parenMap; | |
| public ValidParentheses(){ | |
| parenMap = new HashMap<Character, Character>(); | |
| parenMap.put(')', '('); | |
| parenMap.put('}', '{'); | |
| parenMap.put(']', '['); | |
| } | |
| public boolean isValid(String str){ | |
| Stack<Character> stk = new Stack<Character>(); | |
| for(int i=0; i < str.length(); i++){ | |
| Character ch = str.charAt(i); | |
| if(ch == '(' || ch == '{' || ch == '['){ | |
| stk.push(ch); | |
| } | |
| else if(ch == ')' || ch == '}' || ch == ']'){ | |
| if(stk.isEmpty()) | |
| return false; | |
| Character popedChar = stk.pop(); | |
| if(popedChar != parenMap.get(ch)) | |
| return false; | |
| } | |
| else{ | |
| throw new IllegalArgumentException("Not a valid input"); | |
| } | |
| } | |
| return stk.isEmpty(); | |
| } | |
| @Test | |
| public void basicTest(){ | |
| ValidParentheses vp = new ValidParentheses(); | |
| assertTrue("Valid parens", vp.isValid("{([])}")); | |
| assertTrue("Valid parens", vp.isValid("{()}")); | |
| assertTrue("Valid parens", vp.isValid("{([(()){}])}{}[]")); | |
| assertFalse("InValid parens", vp.isValid("{([)}")); | |
| assertFalse("InValid parens", vp.isValid("{}([])}")); | |
| assertFalse("InValid parens", vp.isValid("([])}")); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment