Проверьте, эквивалентны ли два математических выражения

Question

Я наткнулся на вопрос в интервью. Я пытался решить это, но не смог придумать решение. Вопрос:

[Изменено] Первая часть: Вам даны два выражения только с оператором «+», проверьте, являются ли данные два выражения математически эквивалентными. Например, «A + B + C» эквивалентно «A + (B + C)».

Вторая часть: Вам даны два выражения только с операторами "+" и "-", проверьте, эквивалентны ли данные два выражения математически. Например, «A + B-C» эквивалентно «A - (- B + C)».

Мой мыслительный процесс: я думал с точки зрения построения дерева выражений из заданных выражений и искал какое-то сходство. Но я не могу найти хороший способ проверить, являются ли два дерева выражений одинаковыми или нет.

Может ли кто-нибудь помочь мне в этом :) Заранее спасибо!

Answer 1

Суммарная переменная рассчитывает до появления открывающей фигурной скобки, рассматривая вычитание как добавление отрицательной переменной. Обрабатывать подвыражения рекурсивно.

Содержимое подвыражений может быть напрямую объединено в счетчики, вам просто нужно правильно учесть знак - для этой задачи нет необходимости создавать фактическое дерево выражений. 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.P.P.P.S.: Исправления, упрощение, лучшее объяснение.

Answer 2

Вы можете анализировать выражения слева направо и приводить их к канонической форме для сравнения простым способом;единственное осложнение состоит в том, что когда вы сталкиваетесь с закрывающей скобкой, вам нужно знать, имел ли перед ней открывающая скобка плюс или минус;Вы можете использовать стек для этого;например:

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 3

Пока операции являются коммутативными, я бы предложил решение распределить заключенные в скобки операции, а затем отсортировать термины по «переменным», а затем запустить агрегатор по ним, и вы должны получить ряд факторов и символов.Тогда просто проверьте набор факторов.