Check for balanced brackets or valid parenthesis in an expression

We are given a string expression that consistes of  characters '(', ')', '{', '}', '[' and ']'. We want to determine if the input string is valid.

An input string is valid if:

• The open bracket is closed by a bracket of same type.
• The open bracket is closed in correct order.
• There is a close bracket for every open bracket and both are of same type.

Examples

Below are examples of balanced brackets or valid parenthesis

•  "()"
•  "()[]{}"
• "([{}])"

Below are examples of unbalanced brackets or invalid parenthesis

• "(]"
• "{()[]"

Approach

1. Initialize an empty stack to keep track of open brackets as you traverse the string.
2. Iterate through the characters of the input string from left to right.
3. For each character:
   1. If it is an open bracket ('(', '{', '['), push it onto the stack.
   2. If it is a closing bracket (')', '}', ']'), check if the stack is empty. If it's empty, return false because there is no matching open bracket.
   3. If there is a matching open bracket at the top of the stack, pop the open bracket from the stack.
4. After processing all characters in the string, check if the stack is empty. If the stack is empty, the string is valid because all open brackets have corresponding closing brackets in the correct order.
5. Return true if the stack is empty (valid) or false if there are unmatched brackets or the stack is not empty at the end.

Complexity

• Time Complexity: O(N), where N is the length of the input string.
• Space Complexity: O(N), where N is the length of the input string.

Java Code

import java.util.Stack;

class ValidParenthesis {

    public static boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                return false; // Invalid character or mismatched brackets.
            }
        }

        return stack.isEmpty(); // The string is valid if the stack is empty at the end.
    }

    public static void main(String[] args) {
        String s1 = "()[]{}";
        String s2 = "()[]{";
        boolean isS1Valid = isValidParentheses(s1);
        System.out.println("Is the input string " + s1 + " valid? : " + isS1Valid);

        boolean isS2Valid = isValidParentheses(s2);
        System.out.println("Is the input string " + s2 + " valid? : " + isS2Valid);
    }
}

Output

Is the input string ()[]{} valid? : true
Is the input string ()[]{ valid? : false