Can someone explain to me the logic of the last part of this code?

Question

I was doing hackerrank and I am trying to understand the solution written by RodneyShag. (Credit: He wrote the solution, not me) I am trying to understand the last part.

import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayDeque;

class Solution {
    public static void main(String[] args) {
        /* Create HashMap to match opening brackets with closing brackets */
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        /* Test each expression for validity */
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String expression = scan.next();
            System.out.println(isBalanced(expression, map) ? "true" : "false" );
        }
        scan.close();
    }

    private static boolean isBalanced(String expression, HashMap<Character, Character> map) {
        if ((expression.length() % 2) != 0) {
            return false; // odd length Strings are not balanced
        }        
        ArrayDeque<Character> deque = new ArrayDeque<>(); // use deque as a stack
        for (int i = 0; i < expression.length(); i++) {
            Character ch = expression.charAt(i);
            if (map.containsKey(ch)) {
                deque.push(ch);
            } else if (deque.isEmpty() || ch != map.get(deque.pop())) {
                return false;
            }
        }
        return deque.isEmpty();
    }
}

The explanation (provided by him) is

Our map only has 3 keys: (, [, { The linemap.containsKey(ch) checks if it's one of the above keys, and if so, pushes it to the deque. The next part of

deque.isEmpty() || ch != map.get(deque.pop())

checks if we have a valid expression. Since at this point, we know the character is not (, [, or {, so we must have a valid closing brace. if

1) our deque is empty, and we just read a closing brace, then we have an invalid expression (and return false)

2) if the closing brace does not match the opening brace that we popped off the deque, then we have an invalid expression (and return false)

I understand that Character ch = expression.charAt(i); is supposed to : check whether each variable at expression is = to variable in map Character.

Why is it only ([{ in map? Isn't there ( ) [ ] { } in map?

A map has keys and values, the keys are only `( [ {`, the corresponding right characters are values — Joakim Danielson, May 23 '20 at 08:26
The closing brackets _are_ in the map, as _values_. Do you mean you think that the map should additionally have the key value pairs `(')', '('), (']', '['), ('}'. '{')`? — Sweeper, May 23 '20 at 08:29
You might want to be careful about using `!=` with Objects even if they are the primitive wrappers. https://ideone.com/CaG5ph — matt, May 23 '20 at 09:51
I’m sorry but why would Deque.isEmpty() return true if you push(ch) into the deque? Wouldn’t it never be empty? @matt — Isabel, May 26 '20 at 12:57
I don't know why you've tagged me with that comment. I was just pointing out you have a `!=` to compare two Object's. If you `push(ch)` then the dequeue will not be empty unless you remove the Character. — matt, May 26 '20 at 13:18
@matt sorry i meant to ask you why the code is deque.isEmpty() when there is no removal of character in the code. As I understand isEmpty() will return true if the deque is empty and false if it isn’t. So after the if loop where it adds the opening brackets, and lets say it doesn’t return false, it would go to return isEmpty(). But it wouldn’t return true because the opening brackets were never removed? I meant to ask you that. Sorry I didn’t mean to do any harm. Thank you and have a nice day. — Isabel, May 26 '20 at 14:59
No harm, I was just trying to clarify. Note that you have a `pop` in there that removes an element. So you check, `deque.isEmpty()` which is false, then you check `ch != map.get(deque.pop())` which removes the element. So if your deque only had one element, it is now empty. — matt, May 26 '20 at 15:08

Progman · Accepted Answer · 2020-05-23T10:13:27.160

The map is use to specify which character is the closing bracket given an opening bracket. So when you write

map.get('(')

you get the character ) as defined with

map.put('(', ')');

at the initialization.

What the ch != map.get(deque.pop()) line is checking is if the character ch is an expected closing bracket based on the top value of the stack. To make it more clear/verbose the else if() part can be rewritten as this:

if (map.containsKey(ch)) {
    deque.push(ch);
} else {
    // 'ch' must be one of ), ] or } (or something completely different) at this point

    if (deque.isEmpty()) {
        // stack is empty, but shouldn't, so return false
        return false;
    }

    Character lastOpeningBracket = deque.pop(); // is one of (, [ or {
    Character expectedClosingBracket = map.get(lastOpeningBracket); // is one of ), ] or }
    Character actualReadCharacter = ch; // only for verbosity
    if (!expectedClosingBracket.equals(actualReadCharacter)) {
        System.out.println("The character "+actualReadCharacter+" was read from\n"+
                           "the string, but it should be\n"+
                           "a "+expectedClosingBracket+" character\n"+
                           "because the last opening bracket was\n"+
                           "a "+lastOpeningBracket); // only for verbosity
        return false;
    }
}

(be careful for comparing char and Character, see @matt's comment and What is the difference between == and equals() in Java?. Also check the Character cache which might be used here)

Your "only for verbosity" bit actually has an effect though. It means you'll be comparing chars instead of Characters. — matt, May 23 '20 at 09:54
@matt Good catch, changed it to `Character` to be more close to the original code. — Progman, May 23 '20 at 10:06
@Isabel That is only the `if` statement. The remaining `for()` loop and the `return deque.isEmpty();` from the `isBalanced()` method is still there. — Progman, May 23 '20 at 16:37
I’m sorry but why would Deque.isEmpty() return true if you push(ch) into the deque? Wouldn’t it never be empty? @Progman — Isabel, May 26 '20 at 09:09
@Isabel `deque.pop()` will remove the element from the queue, see https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html#pop(). So `push()` will add it and `pop()` will remove it. — Progman, May 26 '20 at 17:27

Can someone explain to me the logic of the last part of this code?

1 Answers1