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)

Answer 1

import java.util.Stack;
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;
}

public static void main(String[] args) {
        String s = "{()}[]";
        if (ispar(s))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

use stack.peek() == '{' bracket check first in if conduction then stack. Peek () == 'c' bracket check to avoid this EmptyStackException Because JVM will check { Bracket inside peek method instance of ( Bracket.

Try this it work for me.

Answer 2

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

Answer 3

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;

 ...

Answer 4

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.