Мне дана строка 2*x + 5 - (3*x-2)=x + 5, и мне нужно решить ее для x. Мой мыслительный процесс заключается в том, что я бы преобразовал его в дерево выражений, что-то вроде
=
/ \
- +
/\ /\
+ - x 5
/\ /\
* 5 * 2
/\ /\
2 x 3 x
Но как мне фактически уменьшить дерево отсюда? Любые другие идеи?
Вы должны уменьшить его, используя аксиомы из алгебры
a * (b + c) -> (a * b) + (a * c)
Это делается путем проверки типов каждого node в дереве проходов. После того, как предмет полностью расширен в термины, вы можете проверить, что они фактически линейны и т.д.
Значения в дереве будут либо переменными, либо числами. Не так просто представить их как классы, наследующие от некоторого класса AbstractTreeNode, потому что cplusplus не имеет множественной отправки. Так что лучше сделать это "c".
enum NodeType {
Number,
Variable,
Addition //to represent the + and *
}
struct Node {
NodeType type;
//union {char*, int, Node*[2]} //psuedo code, but you need
//something kind of like this for the
//variable name ("x") and numerical value
//and the children
}
Теперь вы можете запросить их типы node и его дочерних элементов с помощью флага switch.
Как я уже говорил ранее - идиоматический код С++ использовал бы виртуальные функции, но не нуждался в необходимой множественной диспетчеризации, чтобы решить эту проблему. (Вам все равно нужно сохранить тип)
Затем вы группируете термины и т.д. и решаете уравнение.
У вас могут быть правила для нормализации дерева, например
constant + variable -> variable + constant
Положил бы x всегда слева от термина. Тогда x * 2 + x * 4 легче упростить
var * constant + var * constant -> (sum of constants) * var
В вашем примере...
Сначала упростите '=', переместив термины (согласно приведенному выше правилу)
Правая часть будет равна -1 * (x + 5), становясь -1 * x + -1 * 5. Левая часть будет сложнее - рассмотрим замену a-b на a + -1 * b.
В конце концов,
2x + 5 + -3x + 2 + -x + -5 = 0
Затем вы можете группировать термины, когда захотите. (Сканирование вдоль и т.д.)
(2 + -3 + -1) x + 5 + 2 + -5 = 0
Суммируйте их, и когда у вас есть mx + c, решите его.
Предполагая, что у вас есть уравнение первого порядка, проверьте все листья на каждой стороне. На каждой стороне есть два бункера: один, чтобы сложить все листья, содержащие кратное X, и один для всех листьев, содержащих кратные константы. Либо добавьте в корзину, либо умножьте каждый бит, когда вы увеличите дерево вдоль каждой ветки от листьев. Вы получите что-то, что концептуально похоже на
a*x + b = c*x + d
В этот момент вы можете просто решить
x = (d - b) / (a - c)
Предполагая, что уравнение может свести к f (x) = 0 и f (x) = a * x + b.
Вы можете преобразовать все листья в дереве выражений в f (x), например: 2 → 0 * x + 2, 3 * x → 3 * x + 0, тогда вы можете выполнить арифметические операции f ( x) в дереве выражений. наконец, решим уравнение f (x) = 0.
Если функция намного сложнее полинома, вы можете выполнить двоичный поиск по x и используя дерево выражений для вычисления левой и правой сторон уравнения.