Problem:

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form “(U)” where U is a properly nested string;
S has the form “VW” where V and W are properly nested strings.

For example, string “(()(())())” is properly nested but string “())” isn’t.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = “(()(())())”, the function should return 1 and given S = “())”, the function should return 0, as explained above.

Assume that:

N is an integer within the range [0..1,000,000];
string S consists only of the characters “(” and/or “)”.

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Solution:

public class ParenthesisMatching {
                public static void main(String[] args) {
                                Scanner scan = new Scanner(System.in);
                
                        /* Create Stack */
                                Stack<Character> stack = new Stack<Character>();
                                System.out.println("Parenthesis Matching Test\n");

                                /* Accepting expression */
                                System.out.println("Enter expression");
                                String exp = scan.next();

                                int len = exp.length();
                                for (int i = 0; i < len; i++) {
                                                char ch = exp.charAt(i);
                                                if (ch == '(') {
                                                                stack.push(ch);
                                                } else if (ch == ')') {
                                                                if(stack.peek() == '(') {
                                                                                stack.pop();
                                                                } else {
                                                                                break;
                                                                }
                                                }            
                                }
                                
                                if(stack.isEmpty() ) {
                                                System.out.println("Balanced parenthis !!");
                                } else {
                                                System.out.println("Not Balanced ");
                                }
                }
}