3
\$\begingroup\$

I am working on a parenthesis checker program in Java that reads in a text stream from standard input and uses a stack to determine whether or not its parentheses are properly balanced. For example, this should print true for [()]{}{[()()]()} and false for [(]). I have made a stack class of my own:

public class Stack {
    private char items[];
    private int top;

    Stack(int n){
        items = new char[n];
        top = -1; 
    }

    void push(char c){
        if(top == items.length-1){
            System.out.println("Stack full.");
            return;
        }
        top++;
        items[top] = c;
    }

    char pop(){
        if(isEmpty()){
            System.out.println("Stack empty");
            return (char)0;
        }
        char p;
        p = items[top];
        top--;
        return p;
    }

    boolean isEmpty(){
        if(top == -1)
            return true;
        else    
            return false;
    }
}

This is my code for the parenthesis class:

public class Parenthesis {
    public static void main(String args[]) throws IOException{
        int size;
        String str;
        Boolean isValid;
        BufferedReader br = 
                new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter Expression:");
        try{
            str = br.readLine();
        }catch(IOException i)
        {
            System.out.println("Invalid Input");
            str ="";

        }
        if(checkValid(str))
            System.out.println("Valid::All Parentheses are balanced.");
        else
            System.out.println("Invalid::Parentheses are not balanced.");

    }

    public static Boolean checkValid(String str){
        char sym,prev;
        Stack s = new Stack(str.length());
        for(int i=0; i<str.length();i++){
            sym = str.charAt(i);
            if(sym == '(' || sym=='{' || sym=='['){
                s.push(sym);
            }
            if(sym == ')' || sym=='}' || sym==']'){
               if(s.isEmpty()){
                   return false;
                }
               else{
                    prev = s.pop();
                    if(!isPairMatch(prev,sym))
                        return false;
               }
            }

        }
        if(!s.isEmpty())
            return false;
        return true;
    }
    public static boolean isPairMatch(char character1, char character2){
        if(character1 == '(' && character2 == ')')
            return true;
        else if(character1 == '{' && character2 == '}')
            return true;
        else if(character1 == '[' && character2 == ']')
            return true;
        else
            return false;
    }
}

Is my way of handling the IOException right?
I don't think there will a stack overflow ever, as the size of my stack is the string length.. And only if the stack is not empty, then only the checkValid method is going for a s.pop() operation. So should I remove the overflow and underflow check within the stack class, as the are redundent and never occurs?? I'm also curious to know if this is a good way of doing it. Any suggestions are welcome.

\$\endgroup\$
2
\$\begingroup\$

Stack class

  • The naming of the constructors inputparameter could be changed to either size or capacity.
  • The if..else statement inside the isEmpty() method can be replaced by simply returning (top == -1) like Govind Singh Nagarkoti stated in his answer.
  • if a stack is poped and is empty an exception should be thrown.
  • if an item is pushed on the stack and the stack is full an exception should be thrown or the stack should be made bigger.
  • The pop() method could be made shorter at the cost of readability like

    char pop(){
        if(isEmpty()){ 
            throw new java.util.EmptyStackException("Stack empty");
        }
        return items[top--];
    }
    

    Why can this be done ? Because the flow is: first getting the item at pos followed by decrementing pos.

checkValid() method

public static Boolean checkValid(String str){
    char sym,prev;
    Stack s = new Stack(str.length());
    for(int i=0; i<str.length();i++){
        sym = str.charAt(i);
        if(sym == '(' || sym=='{' || sym=='['){
            s.push(sym);
        }
        if(sym == ')' || sym=='}' || sym==']'){
           if(s.isEmpty()){
               return false;
            }
           else{
                prev = s.pop();
                if(!isPairMatch(prev,sym))
                    return false;
           }
        }

    }
    if(!s.isEmpty())
        return false;
    return true;
}  

Refering to

           if(s.isEmpty()){
               return false;
            }
           else{
                prev = s.pop();
                if(!isPairMatch(prev,sym))
                    return false;
           }  

Here the else isn't needed, as if the stack is empty it will return. So this can be refactored to just

if(s.isEmpty()){
    return false;
 }

 prev = s.pop();
 if(!isPairMatch(prev,sym)){
     return false;
 }  

At the end of the method you have

    if(!s.isEmpty())
        return false;
    return true;
}  

which can be refactored to

return s.isEmpty();  

You are calling two times the str.length() method. Better way is to call it once and store the result in a local variable.

The opening and closing parenthesis should be stored inside a final char array. The checking if the char is inside one of these arrays can be extracted to a own method.

After doing this your refactored method looks like

private final static char[] openingParenthesis = new char[]{'{', '[', '('};
private final static char[] closingParenthesis = new char[]{'}', ']', ')'};

public static Boolean checkValid(String str) {
    char sym, prev;

    int length=str.length();
    Stack s = new Stack(length);

    for (int i = 0; i < length; i++) {
        sym = str.charAt(i);

        if (isOpeningParenthesis(sym)) {
            s.push(sym);
        } else if (isClosingParenthesis(sym)) {

            if (s.isEmpty()) {
                return false;
            }
            prev = s.pop();
            if (!isPairMatch(prev, sym)) {
                return false;
            }
        }
    }
    return s.isEmpty();
}

private static boolean isClosingParenthesis(char character) {
    return isContainedInArray(character, closingParenthesis);
}

private static boolean isOpeningParenthesis(char character) {
    return isContainedInArray(character, openingParenthesis);
}

private static boolean isContainedInArray(char character, char[] characters) {
    for (char c : characters) {
        if (character == c) {
            return true;
        }
    }
    return false;
}  

You can also remove the throws IOException from the main() method, as you catch it. You shoulc extract the reading from the System.in to a separate method also, as your main() is doing a little to much.

private static String readInput(String statement) {
    BufferedReader br = 
                new BufferedReader(new InputStreamReader(System.in));
    System.out.println(statement);
    try{
        return br.readLine();
    }catch(IOException i)
    {
        return "";
    }
} 

after removing the unused size and isValid variable, your main() method would look like

public static void main(String args[]) {

    String input = readInput("Enter Expression:");

    if(checkValid(input)){
        System.out.println("Valid::All Parentheses are balanced.");
    } else {
        System.out.println("Invalid::Parentheses are not balanced.");
    }
}  

Also you should consider to rename the checkValid() method to something more meaningful like containsBalancedParentheses().

\$\endgroup\$
  • \$\begingroup\$ what about the isContainedInArray() method? and what will happen to the isPairMatch()? \$\endgroup\$ – SouvikMaji Nov 4 '14 at 13:11
  • \$\begingroup\$ should not readInput() be a static method? \$\endgroup\$ – SouvikMaji Nov 4 '14 at 13:12
  • \$\begingroup\$ @rick112358 what exactly is your question ? \$\endgroup\$ – Heslacher Nov 4 '14 at 13:12
  • \$\begingroup\$ @rick112358 I usually wouldn't use any static method here except the main. I have not used an IDE for this, so I forgot to add the static. \$\endgroup\$ – Heslacher Nov 4 '14 at 13:14
  • \$\begingroup\$ What is the structure of isContainedInArray() and what changes I have to make in isPairMatch() to use isContainedInArray()? \$\endgroup\$ – SouvikMaji Nov 4 '14 at 13:18
2
\$\begingroup\$

A little code reduce in two functions:

char pop(){
    if(isEmpty()){
        System.out.println("Stack empty");
        return (char)0;
    }
    return items[top--];
}

boolean isEmpty(){
    return top == -1;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.