Java – Valid Parentheses

This is one of the most common datastructure interview questions and to validate parenthesis.

Examples of valid parentheses: (()){}{}

Examples of Invalid parentheses : ({) or {(((())))

Problem:
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.

Solution: Alogorithem for Valid Parentheses

• This solution is to use Stack Data structure to keep track of the parentheses.
• Opening parenthesis will be pushed onto the stack.
• For closing parenthesis, it will be compared with top element of stack.
• If they match, the opening parenthesis is popped from the stack.
• If they don’t match, the function returns false
• At the end, if the stack is empty, the parentheses are balanced and the function returns true.

package org.javasavvy.datastructures.tutorials;
import java.util.Stack;
//Javasavvy
public class ValidParenthesis {

	public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (stack.isEmpty()) {
                return false;
            } else if (c == ')' && stack.peek() != '(') {
                return false;
            } else if (c == '}' && stack.peek() != '{') {
                return false;
            } else if (c == ']' && stack.peek() != '[') {
                return false;
            } else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
	
	public static void main(String[] args) {
		ValidParenthesis validParent= new ValidParenthesis();
		System.out.println(validParent.isValid("{}((())){}"));
		
	}
}

In the above example, it will print true or false.

Thanks for Reading…