Why aren't escape characters working for replace all brackets?

Question

I'm trying to replace all brackets with their opposite facing bracket as my take of solving the coding challenge on Hackerrank.com found here.

I think have a solution to the challenge, but I can't seem to get the replace all function to work properly on my function. I've tried using Pattern.quote(String) as well as the escape backslashes, but for some reason my brackets are not being replaced.

public class Solution {

    public static boolean isBalanced(String expression) {

        if(expression.length() %2 != 0) {
            return false;
        }
        else {

            int middle = expression.length() /2;
            String open = expression.substring(0,middle);
            String close = expression.substring(middle);

            close.replaceAll("\\)", "\\(");
            close.replaceAll(Pattern.quote("}"),"{");
            close.replaceAll(Pattern.quote("]"), "[");
            new StringBuilder(close).reverse().toString();

            if(close.equals(open))
                return true;
            else
                return false;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            String expression = in.next();
            System.out.println( (isBalanced(expression)) ? "YES" : "NO" );
        }
    }
}

Edit: I tested the code with a print statement after the line new StringBuilder(close).reverse().toString();

Input:

3
{[()]}
{[(])}
{{[[(())]]}

Output:

)]}
NO
])}
NO
))]]}}
NO

I tested it using print statements. The String does not change at all. — Remixt, Oct 05 '17 at 19:23

score 2 · Accepted Answer · answered Oct 05 '17 at 19:26

String objects in Java are immutable, so executing a replace command on one will not change the source String, but rather returns a new String that has been modified.

make your lines like this

close.replaceAll("\\)", "\\(");

instead look like this

close = close.replaceAll("\\)", "\\(");

to update the value of the close variable with a modified String object.

Likewise, the String being created here is being assigned to nothing and will be discarded:

new StringBuilder(close).reverse().toString();

You need to assign the created String somewhere, like

close = new StringBuilder(close).reverse().toString();

I can't believe I made such a silly mistake. Thanks for catching it! — Remixt, Oct 05 '17 at 19:31

score 2 · Answer 2 · answered Oct 05 '17 at 19:27

Your solution is fundamentally wrong, because it is prone to false positives.

Specifically, this string will produce a "YES", while the string is clearly unbalanced:

[({{(]

After you split the string in half you will have "[({" and "{(]". After replacing characters in the closing part you will have "{([", which becomes "[({" after reversal. The result of transformation matches the first half of the string, so your code would incorrectly conclude that brackets inside string are matched.

Thanks for the tip on the challenge! I'd still like to figure out why my code won't return true in any case though. — Remixt, Oct 05 '17 at 19:30

Why aren't escape characters working for replace all brackets?

2 Answers2