Empty Stack Exception

Question

class Solution{
static boolean ispar(String x){
    char [] arr = x.toCharArray();
    int length = arr.length;
    Stack<Character> stack = new Stack<>();
    
    boolean isBalanced = true;
    if(arr[0] == '}' || arr[0] == ')' || arr[0] == ']'){
         isBalanced = false;
    }
    else{   
        for(int i=0; i<length; i++){
            char bracket = arr[i];
        
            if(bracket == '{' || bracket =='(' || bracket == '['){
                stack.push(bracket);
            }
            else if(!stack.empty() && 
                ((char) stack.peek() == '(' && (bracket == ')'))
                    || ((char) stack.peek() == '{' && bracket == '}')
                    || ((char) stack.peek() == '[' && bracket == ']')
                    ){
                stack.pop();
            }
            else{
            isBalanced = false;
            }
    }
    if(stack.empty()){
        isBalanced = true;            
   }
   else{
       isBalanced = false;
   }
 } 
 return isbalanced;
}
}

I am learning Stack data structure. And this is the first problem I am trying to solve but it is giving me this exception :

Exception in thread "main" java.util.EmptyStackException
at java.base/java.util.Stack.peek(Stack.java:102)
at Solution.ispar(File.java:57)
at Driverclass.main(File.java:23)

I would recommend debugging the program yourself, it will be a lot quicker and more useful. There's a great article about it here: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Henry Twist, Aug 25 '21 at 14:38
The issue is with your `else if` block, `else if(!stack.empty() && ((char) stack.peek() == '(' && (bracket == ')') || ((char) stack.peek() == '{' && bracket == '}') || ((char) stack.peek() == '[' && bracket == ']')))` it need to change like this, and also `return isBalanced;` should be in last `return` — Maneesha Indrachapa, Aug 25 '21 at 14:40

Sash Sinha · Answer 1 · 2021-08-25T15:57:58.863

Here's an attempt to correct your code without changing your core attempt:

import java.util.Stack;

class Solution {
    public boolean isBalancedBrackets(String str) {
        char[] arr = str.toCharArray();
        Stack<Character> stack = new Stack<>();

        if (arr[0] == '}' || arr[0] == ')' || arr[0] == ']') {
            return false;
        } else {
            for (char bracket : arr) {
                if (bracket == '{' || bracket == '(' || bracket == '[') {
                    stack.push(bracket);
                } else if (!stack.empty() && 
                        (bracket == ')' && stack.peek() == '(' ||
                         bracket == '}' && stack.peek() == '{' ||
                         bracket == ']' && stack.peek() == '[')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.empty();
    }
}

Changes:

Removed the redundant isBalanced variable, you can just return immediately when you detect a mismatch.
For your else-if statement you need to group all the or conditions together, with one set of parentheses. This is the reason you are getting the EmptyStackException. Since you only want to check any of the three conditions if the stack is not empty.
Renamed method.

Also, consider using a Deque over a Stack in the future.

Actually there was enough pairs of parentheses in the nested else-if condition, but they were mis-placed. I think your answer will be more helpful if you explain why the whole bunch of pairs of comparisons needed to be bracketed together for the `!stack.empty()` part to work properly. :) — CiaPan, Aug 25 '21 at 15:30

score 1 · Answer 2 · answered Aug 25 '21 at 17:52

If you want to ommit letters in @Sash Sinha Solution you could add a new field:

private static Set<Character> bracketSet = Set.of('(', ')', '{', '}', '[', ']');

and the method:

public static boolean ommitLetters(Character chr) {
    return bracketSet.contains(chr);
}

to implement it inside the loop:

...

        for (char bracket : arr)
            if (ommitLetters(bracket)) {
                if (bracket == '{' || bracket == '(' || bracket == '[') {
                    stack.push(bracket);
                } else if (!stack.empty() && (bracket == ')' && stack.peek() == '('
                        || bracket == '}' && stack.peek() == '{' || bracket == ']' && stack.peek() == '[')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else
                continue;

 ...

+1 The logical extension of this would be to look into using a HashMap which would remove the requirement for the or statements completely. — Sash Sinha, Aug 25 '21 at 23:08

Andrzej Więcławski · Answer 3 · 2021-08-26T17:41:03.773

@ Sash Sinha - yes, using HashMap removes the requirement for the multi-or statements completely, ex:

public static <K, V> K getKeyFromMapByValue(Map<K, V> map, V value) {
    for (Entry<K, V> entry : map.entrySet())
        if (entry.getValue().equals(value))
            return entry.getKey();
    return null;
}

private static Set<Character> validParenthesisSet = Set.of('(', ')', '{', '}', '[', ']');

public static boolean areParenthesisPaired(String expression) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> parenthesisPairs = new HashMap<>() {
        private static final long serialVersionUID = 6725243592654448763L;
        {
            put('(', ')');
            put('{', '}');
            put('[', ']');
        }
    };

    for (Character actualParenthesis : expression.toCharArray()) {

        if (validParenthesisSet.contains(actualParenthesis))

            if (parenthesisPairs.containsValue(actualParenthesis)) { // must catch only closed
                Character oppositeParenthesis = getKeyFromMapByValue(parenthesisPairs, actualParenthesis);

                if (stack.size() == 0 || stack.peek() != oppositeParenthesis)
                    return false;

                stack.pop();

            } else
                stack.push(actualParenthesis);
    }

    if (stack.size() > 0)
        return false;

    return true;
}

Empty Stack Exception

3 Answers3