Solution:
The problem can be solved by using a stack.
We iterate over the characters of the string,
and for every iteration:
* Declare a character stack S.
* Now traverse the expression string exp.
*** If the current character is a starting bracket
(‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
*** If the current character is a closing bracket
(‘)’ or ‘}’ or ‘]’) then pop from stack and if the
popped character is the matching starting bracket then
fine else parenthesis are not balanced.
* After complete traversal, if there is some starting
bracket left in stack then “not balanced”
Reference:
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/
https://www.callicoder.com/valid-parentheses/
/*
Valid Parentheses problem statement
Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
*/
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class ValidParentheses {
public static boolean isValid(String str) {
Map<Character, Character> parenthesesMapping = new HashMap<>();
parenthesesMapping.put('(', ')');
parenthesesMapping.put('{', '}');
parenthesesMapping.put('[', ']');
Stack<Character> parentheses = new Stack<>();
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(parenthesesMapping.containsKey(c)) {
parentheses.push(c);
} else {
if(parentheses.isEmpty()) {
return false;
}
char target = parentheses.pop();
if(!parenthesesMapping.containsKey(target) || parenthesesMapping.get(target) != c) {
return false;
}
}
}
if(!parentheses.isEmpty()) {
return false;
}
return true;
}
public static void main(String[] args) {
System.out.println("([)]" + isValid("([)]"));
System.out.println("([)]" + isValid("([)]"));
System.out.println("([)]" + isValid("([)]"));
System.out.println("([)]" + isValid("([)]"));
System.out.println("([)]" + isValid("([)]"));
}
}
December 3, 2019
Leave a comment