While everybody would naturally accept the following lines of code on grounds of reference equality and value equality and that String and wrappers override the equals method, it takes some effort at first to accept the behavior of Arrays.equals and Arrays.deepEquals

1
2
3
4
5
6
7
8
9
10
11

Object obj1=new Object();
Object obj2=new Object();
      
String hello1=new String("hello");
String hello2=new String("hello");
      
System.out.println(hello1.equals(hello2)); //returns true
System.out.println(hello1==hello2); //returns false
      
System.out.println(obj1.equals(obj2)); //returns false
System.out.println(obj1==obj2); //returns false

Boring Stuff :-(

First, the similarities

Both Arrays.equals and Arrays.deepEquals are similar in certain behaviors as

1. If they are the same object (reference equality), they return true
2. If either of the compared objects are null, then return false
3. If the array lengths are not equal, then return false
4. They care about order (position)

Next, the differences

Arrays.equals is really just skin deep

Opening up the souce, we could see that the lousy Array.equals just does this

1
2
3
4
5
6
7
8

 for (int i=0; i<length; i++) {
     Object o1 = a[i];
     Object o2 = a2[i];

     if (!(o1==null ? o2==null : o1.equals(o2)))
         return false;
 }

So, it just loops through the given arrays, does a equals on each of the pairs. This means that if you are passing in a String/Wrapper array or any other arrays whose equals method is overridden, then they are equal. Non-equals-overridden classes (derived from Object) will return false.

Arrays.deepEquals looks really deep

From the source, we could understand that Arrays.deepEquals

1. Loops through the input arrays, gets each pair
2. Analyses the type of each pair
3. Delegates the equal deciding logic to one of the overloaded Arrays.equals if they are one of the primitive arrays
4. Delegates recursively to Arrays.deepEquals if it is an Object array
5. Calls the respective object’s equals, for any other object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

for (int i = 0; i < length; i++) {
            Object e1 = a1[i];
            Object e2 = a2[i];

            if (e1 == e2)
                continue;
            if (e1 == null)
                return false;

            // Figure out whether the two elements are equal
            boolean eq;
            if (e1 instanceof Object[] && e2 instanceof Object[])
                eq = deepEquals ((Object[]) e1, (Object[]) e2);
            else if (e1 instanceof byte[] && e2 instanceof byte[])
                eq = equals((byte[]) e1, (byte[]) e2);
           …
           …
            else
                eq = e1.equals(e2);

            if (!eq)
                return false;
        }
        return true;

Now, the Awesome stuff !!

Equals not overridden (nested and non-nested)

While doing an Arrays.equals for nested or non-nested ‘non-overridden equals’ objects, it is safe to assume that if Arrays.equals return false, then Arrays.deepEquals also return false.

Non-Nested

So, given two arrays

1
2
3

private YourClass[] equalsNotOverriddenArrayNonNested1={new YourClass(), new YourClass()};
private YourClass[] equalsNotOverriddenArrayNonNested2={new YourClass(), new YourClass()};
  

where YourClass is simply

1
2

public class YourClass {
}

then the following assertions are true

1
2

assertFalse(Arrays.equals(equalsNotOverriddenArrayNonNested1, equalsNotOverriddenArrayNonNested2));
assertFalse(Arrays.deepEquals(equalsNotOverriddenArrayNonNested1, equalsNotOverriddenArrayNonNested2));

Nested

Also given two arrays,

1
2

private Object[] equalsNotOverriddenArrayNested1={new YourClass(), new YourClass[]{new YourClass()}};
private Object[] equalsNotOverriddenArrayNested2={new YourClass(), new YourClass()};

the following assertions are true

1
2
3

 assertFalse(Arrays.equals(equalsNotOverriddenArrayNested1, equalsNotOverriddenArrayNested2));
  assertFalse(Arrays.deepEquals(equalsNotOverriddenArrayNested1, equalsNotOverriddenArrayNested2));
  

Equals overridden

Non-Nested

While doing an Arrays.equals for non-nested ‘overridden equals’ objects, it can be said that if Arrays.equals is true, then Arrays.deepEquals also return true.

Given two String arrays

1
2

private Object[] equalsOverriddenArrayNonNested1={"101","201"};
private Object[] equalsOverriddenArrayNonNested2={"101","201"};

the following assertions are true

1
2

assertTrue(Arrays.equals(equalsOverriddenArrayNonNested1, equalsOverriddenArrayNonNested2));
assertTrue(Arrays.deepEquals(equalsOverriddenArrayNonNested1, equalsOverriddenArrayNonNested2));

since they are just one-to-one equals call on each pair.

Nested

Interesting scenario : While doing an Arrays.equals for nested ‘overridden equals’ objects, if Arrays.equals is false, then Arrays.deepEquals need not be false.

Consider two Object arrays which has two values - a String and a String array

1
2

private Object[] equalsOverriddenArrayNested1={new String("hello"), new String[]{new String("hello")}};
private Object[] equalsOverriddenArrayNested2={new String("hello"), new String[]{new String("hello")}};

you can notice that the Arrays.equals return false while Arrays.deepEquals return true

1
2

assertFalse(Arrays.equals(equalsOverriddenArrayNested1, equalsOverriddenArrayNested2));
assertTrue(Arrays.deepEquals(equalsOverriddenArrayNested1, equalsOverriddenArrayNested2));

The result for Arrays.deepEquals is logical since each (from the source), the method loops through each pair of elements, checks whether it is an array type and calls deepEquals on each of the pair. If it is an non-array type, then it just calls the equals on the object.

However, the result of Arrays.equals is tricky but at the same time obvious. The Arrays.equals method blindly calls equals on each pair and since the second arguments String[] are of Object type (whose equals is not overridden), it checks for reference equality and fails !!

The entire testcase can be found below :

When I wrote this write-up on evaluating an infix expression having multiple digits, I was lazy to do it for expressions with parentheses. So, here it comes.

As usual, here is the javascript version.

Just like the non-paranthesized version, this algorithm is just the two stack algorithm modified to accommodate parentheses and multiple digits. Floating points aren’t supported intentionally nor is tested. However, I don’t see any reason why it should not work (provided you change the variable types to accommodate a floating point number).

The algorithm goes like this :

1. Initialize two stacks - one for holding values and one for holding operators
2. Read the input expression from left to right - one character at a time. 
3. If the character is a space, ignore
4. If the character is a number, then append it to an accumulating variable 
   (don't push it to the stack yet)
5. If the character is an operator or a right parenthesis, push the accumulated number 
   to the value stack and reinitialize the accumulator.

    5a. If the current operator is a left parenthesis, push it to the expression stack 
        and continue to the next character in the expression. 

    5b. If the current operator is a right parenthesis, then evaluate the stacks 
        until the first left parenthesis is reached. Push the result back to the value stack 

    5b. If the current operator is of higher precedence than the first item in the operator stack,
        then safely ignore and read further. 

    5c. If the current operator is of lower precedence than the first item in the operator 
        stack (peek view), then evaluate the previous set (two from value stack and one 
        from operator stack) and insert the result into the value stack

    5d. Finally, insert the current operator to the operator stack

Note : the operator level for right parenthesis is kept at ‘0’ to retain operator precedence while the operator level of left paranthesis is kept at ‘3’ (or anything higher than all the operators) to be the least in the precedence. The only purpose of storing the left brackets in the expression stack is for identifying the beginning of the paranthesized sub-expression.

1

public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]

A Groovy implementation is here :

If you are looking for evaluating an infix expression with parantheses, don’t waste your time here. Visit my other fresh write up here

These images have been running around Facebook for a while now. Though it is eye-damaging primary level arithmetic, it is kind of sweet to write it as a program. Just for the fun of it, I created an html page driven by a javascript implementation. Here is the link.

So, essentially the idea is to evaluate the infix notation in a natural way - respecting the operator precedence. (If you consider this as a puzzle, then there are other variations which involves evaluating the expression in such a way that the result is a maximum value/minimum value)

Please note that the algorithm (and therefore, the program), as it stands does not handle parentheses. This is just a two-stack algorithm with a small variation to accommodate numbers more than a digit.

The algorithm goes like this :

1. Initialize two stacks - one for holding values and one for holding operators
2. Read the input expression from left to right - one character at a time. 
3. If the character is a space, ignore
4. If the character is a number, then append it to an accumulating variable 
   (don't push it to the stack yet) 
5. If the character is an operator, push the accumulated number to the value stack and 
   reinitialize the accumulator.

    5a. If the current operator is of higher precedence than the first item in the operator stack,
        then safely ignore and read further.

    5b. If the current operator is of lower precedence than the first item in the operator 
        stack (peek view), then evaluate the previous set (two from value stack and one 
        from operator stack) and insert the result into the value stack

    5c. Finally, insert the current operator to the operator stack

A Groovy implementation is here :