Code Destine

Problem Statement

You have given a string consist of characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘ only. Write a program to find out if the input string is valid or not.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets, like { }, ( ), [ ].
2. Open brackets must be closed in the correct order, like {()}

Note: Empty string is also considered valid.

Example 

Input :- ()[]{}
Output :- true

Input :- ([)]
Output :- false

Input :- {[]}
Output :- true

Solution

The Stack data structure can be used to solve this problem, following are the steps :-

1. Create the character array from the input String.
2. Iterate through the character array and at each iteration, check if the character is a open bracket ( ‘(‘, ‘[‘, ‘{‘ ) or close bracket ( ‘)‘, ‘]‘, ‘}‘).
3. If the character is an open bracket, then push the character on the top of the stack.
4. If the character is a close bracket and character at the top of the stack is equal to it, then pop the top element of the stack.
5. If the stack is empty after completion of the 2nd, 3rd and 4th step, then the string is valid and the result is true otherwise result is false.

Program

import java.util.Stack;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		boolean result = main.isValid("(){[]}");
		System.out.print(result);										
	}  
	
	/* Solution */    
	public boolean isValid(String s) {

		char[] array = s.toCharArray();
		Stack<Character> stack = new Stack<>();

		for (int i = 0; i < array.length; i++) {

			switch (array[i]) {
			case '(':
			case '[':
			case '{':
				stack.push(array[i]);
				break;
			case ')':
				if (stack.size() > 0 && stack.peek() == '(') {
					stack.pop();
					break;
				} else {
					return false;
				}
			case ']':
				if (stack.size() > 0 && stack.peek() == '[') {
					stack.pop();
					break;
				} else {
					return false;
				}
			case '}':
				if (stack.size() > 0 && stack.peek() == '{') {
					stack.pop();
					break;
				} else {
					return false;
				}
			}
		}

		if(stack.size() == 0) {
			return true;
		}
		return false;
	}
}

Result

true 

Similar Post

1. Next Greater Element
2. Implement Stack using Queues
3. Implement Queue using Stacks

That’s all for Valid Parentheses in Java, If you liked it, please share your thoughts in a comments section and share it with others too.