-1
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)
2
  • 1
    I would recommend debugging the program yourself, it will be a lot quicker and more useful. There's a great article about it here: ericlippert.com/2014/03/05/how-to-debug-small-programs Commented Aug 25, 2021 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 Commented Aug 25, 2021 at 14:40

4 Answers 4

3

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.

Sign up to request clarification or add additional context in comments.

2 Comments

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. :)
That's much more informative, IMO. Well done :)
1

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 Comment

+1 The logical extension of this would be to look into using a HashMap which would remove the requirement for the or statements completely.
0

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

Comments

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.