Check for Balanced Parentheses in an Expression

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.

1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) 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.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”


public static boolean isValid(String s) {
	char[] charArray = s.toCharArray();
	HashMap<Character, Character> map = new HashMap<Character, Character>();
	map.put('(', ')');
	map.put('[', ']');
	map.put('{', '}');
	Stack<Character> stack = new Stack<Character>();
	for (Character c : charArray) {
		if (map.keySet().contains(c)) {
		} else if (map.values().contains(c)) {
			if (!stack.isEmpty() && map.get(stack.peek()) == c) {
			} else {
				return false;
	return stack.isEmpty();

Time Complexity: O(n)
Auxiliary Space: O(n) for stack.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation