Check if two mathematical expressions are equivalent

Question

I came across a question in an interview. I tried solving it but could not come up with a solution. Question is:

[Edited] First Part: You are given two expressions with only "+" operator, check if given two expressions are mathematically equivalent. For eg "A+B+C" is equivalent to "A+(B+C)".

Second Part : You are given two expressions with only "+" and "-" operators, check if given two expressions are mathematically equivalent. For eg "A+B-C" is equivalent to "A-(-B+C)".

My thought process : I was thinking in terms of building an expression tree out of the given expressions and look for some kind of similarity. But I am unable to come up with a good way of checking if two expression trees are some way same or not.

Can some one help me on this :) Thanks in advance !

Answer 1

You can parse the expressions from left to right and reduce them to a canonical form for comparison in a straightforward way; the only complication is that when you encounter a closing bracket, you need to know whether its associated opening bracket had a plus or minus in front of it; you can use a stack for that; e.g.:

function Dictionary() {
    this.d = [];
}
Dictionary.prototype.add = function(key, value) {
    if (!this.d.hasOwnProperty(key)) this.d[key] = value;
    else this.d[key] += value;
}
Dictionary.prototype.compare = function(other) {
    for (var key in this.d) {
        if (!other.d.hasOwnProperty(key) || other.d[key] != this.d[key]) return false;
    }
    return this.d.length == other.d.length;
}

function canonize(expression) {
    var tokens = expression.split('');
    var variables = new Dictionary();
    var sign_stack = [];
    var total_sign = 1;
    var current_sign = 1;

    for (var i in tokens) {
        switch(tokens[i]) {
            case '(' : {
                sign_stack.push(current_sign);
                total_sign *= current_sign;
                current_sign = 1;
                break;
            }
            case ')' : {
                total_sign *= sign_stack.pop();
                break;
            }
            case '+' : {
                current_sign = 1;
                break;
            }
            case '-' : {
                current_sign = -1;
                break;
            }
            case ' ' : {
                break;
            }
            default : {
                variables.add(tokens[i], current_sign * total_sign);
            }
        }
    }
    return variables;
}

var a = canonize("A + B + (A - (A + C - B) - B) - C");
var b = canonize("-C - (-A - (B + (-C)))");
document.write(a.compare(b));

Answer 2

Aggregate variable counts until encountering an opening brace, treating subtraction as addition of the negated variable. Handle sub-expressions recursively.

The content of sub-expressions can be directly aggregated into the counts, you just need to take the sign into account properly -- there is no need to create an actual expression tree for this task. The TreeMap used in the code is just a sorted map implementation in the JDK.

The code takes advantage of the fact that the current position is part of the Reader state, so we can easily continue parsing after the closing bracket of the recursive call without needing to hand this information back to the caller explicitly somehow.

Implementation in Java (untested):

class Expression {
   // Count for each variable name
   Map<String, Integer> counts = new TreeMap<>();

   Expression(Srring s) throws IOException {
     this(new StringReader(s));
   }

   Expression(Reader reader) throws IOException {
     int sign = 1;
     while (true) {
       int token = reader.read(); 
       switch (token) {
         case -1:  // Eof
         case ')':
           return;
         case '(':
           add(sign, new Expression(reader));
           sign = 1;
           break;
         case '+':
           break;
         case '-':
           sign = -sign;
           break;
         default:
           add(sign, String.valueOf((char) token));
           sign = 1;
           break;
       }
     }
   }

   void add(int factor, String variable) {
     int count = counts.containsKey(variable) ? counts.get(variable) : 0;
     counts.put(count + factor, variable);
   }

   void add(int sign, Expression expr) {
     for (Map.Entry<String,Integer> entry : expr.counts.entrySet()) {
       add(sign * entry.getVaue(), entry.getKey());
     }
   }

   void equals(Object o) {
     return (o instanceof Expression) 
        && ((Expression) o).counts.equals(counts);
   }

   // Not needed for the task, just added for illustration purposes.
   String toString() {
     StringBuilder sb = new StringBuilder();
     for (Map.Entry<String,Integer> entry : expr.counts.entrySet()) {
       if (sb.length() > 0) {
         sb.append(" + ");
       }
       sb.append(entry.getValue());  // count
       sb.append(entry.getKey());    // variable name
     }
     return sb.toString();
   }
 }

Compare with

new Expression("A+B-C").equals(new Expression("A-(-B+C)"))

P.S: Added a toString() method to illustrate the data structure better.

Should print 1A + 1B + -1C for the example.

P.P.P.P.S.: Fixes, simplification, better explanation.

Answer 3

As long as the operations are commutative, the solution I'd propose is distribute parenthetic operations and then sort terms by 'variable', then run an aggregator across them and you should get a string of factors and symbols. Then just check the set of factors.