2

I'm new to Hacker Rank and I'm currently solving problems in the java stack, I tried to solve this algorithm:

A string containing only parentheses is balanced if the following is true: 1. if it is an empty string 2. if A and B are correct, AB is correct, 3. if A is correct, (A) and {A} and [A] are also correct.

Examples of some correctly balanced strings are: "{}()", "[{()}]", "({()})"

Examples of some unbalanced strings are: "{}(", "({)}", "[[", "}{" etc.

Given a string, determine if it is balanced or not.

And I found the following one liner solution which I couldn't understand can someone explain it please?

class Solution{
     public static void main(String []argh)
     {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            String input=sc.next();
            while(input.length() != (input = input.replaceAll("\\(\\)|\\[\\]|\\{\\}", "")).length());
            System.out.println(input.isEmpty());
        }
        
    }
}
Maurice Perry
  • 9,261
  • 2
  • 12
  • 24
Shtaiwee
  • 69
  • 5
  • 1
    Why are you looking into a solution and not trying it first? Also, why are you looking into a one-liner for a solution that is, firstly, not javaesque at all and secondly, so obfuscated that its just bad? Write your own code, use a stack to store open-closed braces, parentheses and boxes and see that they don't violate validity rules. – vish4071 Mar 31 '22 at 11:31
  • 3
    The funny string in the replaceAll call is a regex. The double slashes are really single slashes (java needs them in strings to indicate that you really want a slash and not an escape character). Have a look here: https://regex101.com/r/70suxF/1 – Robert Harvey Mar 31 '22 at 11:32

2 Answers2

4

The string "\\(\\)|\\[\\]|\\{\\}" given to replaceAll is a regular expression. Half of the backslashes are needed because all of ()[]{} have special meaning in a regex; the other half are needed to escape those backslashes because \ also has special meaning in a string.

Ignoring the backslashes, the pattern is ()|[]|{}, which will match any of the substrings (), [] and {}. The replaceAll call then removes all matches of these by replacing them with the empty string "". This is then repeated until no more matches can be replaced.

On balanced strings, and only on balanced strings, this eventually produces an empty string by removing empty pairs from the inside out. Let's look at an example:

[{()}]()[{}]
  ^^  ^^ ^^  <- these matches are removed
[{}][]
 ^^ ^^ <- then these are removed
[]
^^ <- and finally this one

There is some more obfuscation going on with the way the while loop is written:

while(input.length() != (input = input.replaceAll(...)).length());

To understand this, you need to know that = performs an assignment, but also evaluates to the assigned value. And you need to know that Java always evaluates subexpressions from left to right.

So first, input.length() is evaluated, producing the length of the original string. Then (input = input.replaceAll(...)).length() is evaluated, which does two things: it assigns the next string to input, and it returns the length of that next string.

Finally, the two lengths are compared. If equal, the loop terminates because nothing more can be replaced. If not equal, it means that some matching pair has been removed, and we will do another iteration, now with the new value of input.

Finally, we just check whether the resulting string is empty:

System.out.println(input.isEmpty());
Thomas
  • 174,939
  • 50
  • 355
  • 478
2

replaceAll method needs 2 parameters (regex, replacement); you need to understand regex:

the \\ means whatever the begin is. (\\) the begin must to be '(' and the end must be ')' and whatever between them and like that for rest from regex.

the solution is replacing regex with empty String.

so if your input = (1,2)3( it will be after replacing 3(

AcK
  • 2,063
  • 2
  • 20
  • 27
Jabal
  • 21
  • 2