检查两个数学表达式是否相等

Question

我在面试中遇到了一个问题。我试着解决这个问题，但想不出解决办法。问题是：

编辑第一部分:给你两个只有"+“运算符的表达式，检查给定的两个表达式在数学上是否等价。

第二部分:给你两个只有"+“和"-”运算符的表达式，检查给定的两个表达式在数学上是否等价。例如"A+B-C“等同于"A-(-B+C)”。

我的思维过程:我的想法是从给定的表达式中构建一个表达式树，并寻找某种相似性。但是我不能想出一个好的方法来检查两个表达式树在某种程度上是否相同。

Answer 1

只要操作是可交换的，我建议的解决方案是分配括号操作，然后按“变量”对术语进行排序，然后对它们运行聚合器，您应该得到一个因子和符号字符串。然后只需检查一组因素。

Answer 2

聚合变量会一直计数到遇到左大括号，将减法视为求反变量的加法。递归处理子表达式。

子表达式的内容可以直接聚合到计数中，您只需正确考虑符号--不需要为此任务创建实际的表达式树。代码中使用的TreeMap只是JDK中的一个排序映射实现。

代码利用了当前位置是Reader状态的一部分这一事实，因此我们可以在递归调用的结束括号之后轻松地继续解析，而不需要以某种方式显式地将此信息返回给调用者。

Java实现(未测试)：

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();
   }
 }

与…比较

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

P.S:添加了一个toString()方法来更好地说明数据结构。

对于示例，应该打印1A + 1B + -1C。

P.S.：修复，简化，更好的解释。

Answer 3

您可以从左到右解析表达式，并将其简化为规范化形式，以便以简单的方式进行比较；唯一的复杂之处在于，当您遇到右方括号时，您需要知道其关联的左方括号前面是否有一个加号或减号；为此，您可以使用堆栈；例如：

​

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));

​