Valid parenthesis checking using Stack in java

     Let us solve a common problem called “Valid parentheses”. It is a problem which checks a given string has a valid parenthesis. It means that the parentheses are nested and closed properly. If you use stack for solving this problem, it is good to be effective.

List of parentheses:

‘(‘ , ’)’ , ’[‘ , ’]’ , ’{‘ , ’}’.

Valid usage of parentheses:

• ‘({[]})’
• ‘{[()]}’
• ‘[{()}]’

Let us implement this program in java.

Program:

• ·       Create a stack for finding the opening parenthese.
• ·       Traverse the string character by character.
• ·       Check for opening parenthesis, if occurs,insert(push) the parenthese into stack.
• ·       If it is a closing parenthesis, check the stack is having its opening parenthesis.
• ·       If these two are matching, pop the element from the stack. Otherwise,print the string is invalid.
• ·       Repeat this until the stack become empty.

Here is the program.

import java.util.Stack;

public class ValidParenthesesStackEg {

    public static boolean isValidorNot(String s) {

        Stack<Character> stack1 = new Stack<>();

 

        for (char c : s.toCharArray()) {

            if (c == '(' || c == '{' || c == '[') {

                stack1.push(c);

            } else if (c == ')' || c == '}' || c == ']') {

                if (stack1.isEmpty()) {

                    return false;

                }

                char top = stack1.pop();

                if ((c == ')' && top != '(') ||

                    (c == '}' && top != '{') ||

                    (c == ']' && top != '[')) {

                    return false;

                }

            }

        }

 

        return stack1.isEmpty();

    }

     public static void main(String[] args) {

        String test1 = "({[]})";

        String test2 = "[{()}]";

        String test3 = "{([";

        if(isValidorNot(test1))

        System.out.println(test1 + " is valid");

        else

          System.out.println(test1 + " is invalid");

        if(isValidorNot(test2))

        System.out.println(test2 + " is valid");

        else

          System.out.println(test2 + " is invalid");

       if(isValidorNot(test3))

        System.out.println(test3 + " is valid");

        else

          System.out.println(test3 + " is invalid");

    }

}

Output:

C:\raji\blog>javac ValidParenthesesStackEg.java

C:\raji\blog>java ValidParenthesesStackEg

({[]}) is valid

[{()}] is valid

{([ is invalid

Using the above implementation, it is efficient to find the string is having valid parenthesis. Keep Coding!!