Tuesday, July 1, 2014

Java program to check parenthesis are matching or not.

3:40 PM



Objective: To test whether the input string of a parenthesis is matching or not i.e. we will print output as MATCHING when every opening braces have a matching closing braces  .

Example:

{{[[(())]]}}----Valid 

{{(})}--Invalid

Algorithm: 

1. Take a input string.

2. Traverse the String starting from index '0' to (length-1).

3. Check if the element encountered during traversing is opening braces ?
  • if yes, push that element into stack.
4. If the element encountered is closing braces then
  • Pop an element from stack and check if the popped element is the corresponding opening braces, if no return false. 
  • If yes, do nothing (loop continue).
5.After completion of traversal check if the stack isEmpty() or not? If yes, return true, else return false.


PROGRAM:

import java.util.*;
public class StringTest {
    private static final char LPAREN    = '(';
    private static final char RPAREN    = ')';
    private static final char LBRACE    = '{';
    private static final char RBRACE    = '}';
    private static final char LBRACKET  = '[';
    private static final char RBRACKET  = ']';

    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {

            if      (s.charAt(i) == LPAREN)   stack.push(LPAREN);

            else if (s.charAt(i) == LBRACE)   stack.push(LBRACE);

            else if (s.charAt(i) == LRACKET) stack.push(LBRACKET);

            else if (s.charAt(i) == RPAREN) {
                if (stack.isEmpty())        return false;
                if (stack.pop() != L_PAREN) return false;
            }

            else if (s.charAt(i) == RBRACE) {
                if (stack.isEmpty())        return false;
                if (stack.pop() != LBRACE) return false;
            }

            else if (s.charAt(i) == RBRACKET) {
                if (stack.isEmpty())        return false;
                if (stack.pop() != LBRACKET) return false;
            }

            // ignore all other characters

        }
        return stack.isEmpty();
    }


    public static void main(String[] args) {
Scanner scn=new Scanner(System.in);
        String s = scn.nextLine();
        System.out.println(isBalanced(s));
    }

}



            DOWNLOAD THE ABOVE PROGRAM BY CLICKING HERE.

0 comments :

Post a Comment

 

© 2014 DieHardTechy . All rights resevered. Designed by Diehardtechy