Как бы вы написали программу для уменьшения уравнения?

Question

Возможно, я неверно истолковываю точную формулировку вопроса, о котором я думал , но мне любопытно, как можно сократить уравнение нескольких переменных.

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

Есть ли лучший способ сделать это?

Answer 1

Я бы предположил, что вид сокращений, который они ищут, заключается в том, что что-то вроде (2 + 3) * x должно стать (* 5 x), а не (* (+ 2 3) x).В этом случае вы можете просто распознать, что поддеревья являются постоянными, и рассчитать их.

Вы также можете использовать ассоциативные и коммутативные законы, чтобы сначала попытаться изменить положение вещей, чтобы помочь процессу.Так что 2 + x + 3 станет (+ 5 x), а не (+ (+ 2 x) 3).

Возьмите эту идею так далеко, как вы хотите.Это было преднамеренно дано открытым способом.Я уверен, что они будут рады видеть, что вы автоматически узнаете, что x * x + 2 * x + 1 - это (* (+ 1 x) (+ 1 x)) вместо (+ (+ (* x x) (* 2 x)) 1), но вы можете сделать много хороших сокращений, не переходя туда.

Answer 2

Общее решение - написать переводчик flex \ bison и уменьшить количество разбираемых выражений. Создав поток перевода, вы можете добавить такие правила, как expr * expr + 2 * expr + 1 -> (* expr expr) так же просто, как я пишу здесь.

Answer 3

Одна проблема здесь в том, что каждый считает уменьшенным: например, (я пишу это для лучшей читаемости в инфиксах - но префикс похож на) x * x + x + 2 + 2 * x, одно очевидное сокращение будет x * x+ 3 * x + 2, другой будет (x + 1) * (x + 2).Поскольку это довольно нетривиальные проблемы и из формулировки задания, я бы предположил, что вы приводите свое уравнение в некоторой канонической форме (например, полином, отсортированный с наивысшей степенью наименьшей) (когда у вас есть более одной переменной, возьмите сумму степеней) и уменьшите там коэффициенты (вычислите их при постоянной)).

Будьте осторожны, некоторые оптимизации могут показаться правильными, но не являются общими.Например, не уменьшайте (/ (* xx) x) до x, так как там решение 0 внезапно действует, чего раньше не было.

Answer 4

Вы можете сделать это, используя стек. Это намного проще. Решение размещено здесь

http://bluefintuna.wordpress.com/2008/07/15/infix-prefix/