Parenthesis checker

Question

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.

Answer 1

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().

Answer 2

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;
}