Определения
- простой:
- Описывает выражения без подвыражений (например, "5", "x").
- соединение:
- Описывает выражения, которые имеют подвыражения (например, «3 + x», «1 + 2»).
- константность:
- Независимо от того, имеет ли выражение постоянное значение (например, «5», «1 + 2») или нет (например, «x», «3 + x»).
- внешний узел:
- В дереве выражений - узел, достижимый путем всегда прохода влево или всегда прохода вправо. «Наружный» всегда относительно данного узла; узел может быть «внешним» по отношению к одному узлу, но «внутренним» по отношению к родительскому узлу.
- внутренний узел:
- В дереве выражений - узел, который не является внешним узлом.
Для иллюстрации «внутренних» и «внешних» узлов рассмотрим:
__1__
/ \
2 5
/ \ / \
3 4 6 7
3 и 7 всегда внешние узлы. 6 является внешним относительно 5, но внутренним относительно 1.
Ответ
Трудность здесь заключается скорее в неравном формате выражения, чем во вложении. Если вы используете деревья выражений, пример уравнения 5x+3=(x+(3+(5-3))) будет анализировать:
array(
'=' => array(
'+' => array( // 5x + 3
'*' => array(
5, 'x'
),
3
)
'+' => array( // (x+(3+(5-3)))
'x',
'+' => array( // (3+(5-3))
3,
'-' => array(
5, 3
) ) ) ) )
Обратите внимание, что узлы для двоичных операций являются двоичными, и унарные операции будут иметь унарные узлы. Если бы узлы для бинарных коммутативных операций можно было объединить в n-арные узлы, 5x+3=x+3+5-3 можно было бы проанализировать в:
array(
'=' => array(
'+' => array( // 5x + 3
'*' => array(
5, 'x'
),
3
)
'+' => array( // x+3+5-3
'x',
3,
'-' => array(
5, 3
) ) ) )
Затем вы бы написали рекурсивную функцию после заказа, которая упростила бы узлы. «Пост-заказ» означает, что обработка узла происходит после обработки его дочерних элементов; есть также предварительный порядок (обработка узла перед его дочерними элементами) и упорядочение (обработка некоторых дочерних элементов перед узлом, а остальные - после). Далее следует грубая схема. В нем «вещь: Тип» означает, что «вещь» имеет тип «Тип», а «&» обозначает передачу по ссылке.
simplify_expr(expression : Expression&, operation : Token) : Expression {
if (is_array(expression)) {
foreach expression as key => child {
Replace child with simplify_expr(child, key);
key will also need to be replaced if new child is a constant
and old was not.
}
return simplify_node(expression, operation);
} else {
return expression;
}
}
simplify_node(expression : Expression&, operation : Token) : Expression;
В некотором смысле, настоящая проблема заключается в написании simplify_node. Он может выполнять ряд операций над узлами выражений:
- Если внутренний внучат не соответствует константности другого ребёнка, но его брат или сестра соответствуют, поменяйте местами братьев и сестер. Другими словами, сделайте лишний человек внешним узлом. Этот шаг готовится к следующему.
+ + + +
/ \ / \ / \ / \
\+ 2 ---> + 2 + y ---> + y
/ \ / \ / \ / \
1 x x 1 x 1 1 x
Если узел и дочерний элемент - это одна и та же коммутативная операция, узлы можно переставить. Например, есть вращение:
+ +
/ \ / \
\+ c ---> a +
/ \ / \
a b b c
Это соответствует изменению «(a + b) + c» на «a + (b + c)». Вы захотите повернуть, когда «a» не совпадает с константой «b» и «c». Это позволяет применить следующее преобразование к дереву. Например, этот шаг преобразует «(x + 3) +1» в «x + (3 + 1)», поэтому следующий шаг может преобразовать его в «x + 4».
Общая цель - сделать дерево с постоянными детьми в качестве братьев и сестер. Если коммутативный узел имеет двух постоянных потомков, они могут вращаться рядом друг с другом. Если у узла есть только один потомок const, сделайте его дочерним, чтобы узел, находящийся выше в иерархии, потенциально мог объединить узел const с другим из const потомков предка (т. Е. Узлы const всплывают до тех пор, пока они не станут родственниками, и в этот момент они сочетаются как пузыри в газировке).
- Если все дочерние элементы постоянны, оцените узел и замените его результатом.
Обработка узлов с более чем одним составным дочерним и n-арными узлами, оставленными в качестве упражнений для читателя.
Объектно-ориентированная альтернатива
Подход OO (использование объектов, а не массивов для построения деревьев выражений) будет иметь ряд преимуществ. Операции будут более тесно связаны с узлами, например; они будут свойством объекта узла, а не ключом узла. Также было бы проще связать вспомогательные данные с узлами выражений, что было бы полезно для оптимизации. Вам, вероятно, не понадобится слишком углубляться в парадигму ООП, чтобы реализовать это. Можно использовать следующую простую иерархию типов:
Expression
/ \
SimpleExpr CompoundExpr
/ \
ConstantExpr VariableExpr
Существующие свободные функции, управляющие деревьями, станут методами.Интерфейсы могут выглядеть примерно так, как в следующем псевдокоде.В нем:
Child < Parent означает, что «дочерний элемент» является подклассом «родительского».- Свойства (такие как
isConstant) могут быть методами или полями;в PHP вы можете реализовать это, используя перегрузку . (...){...} обозначают функции с параметрами между круглыми скобками и телом между скобками (очень похоже на function (...){...} в Javascript).Этот синтаксис используется для свойств, которые являются методами.Простые методы просто используют скобки для тела метода.
Теперь для примера:
Expression {
isConstant:Boolean
simplify():Expression
}
SimpleExpr < Expression {
value:Varies
/* simplify() returns an expression so that an expression of one type can
be replaced with an expression of another type. An alternative is
to use the envelope/letter pattern:
http://users.rcn.com/jcoplien/Patterns/C++Idioms/EuroPLoP98.html#EnvelopeLetter
http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Envelope_Letter
*/
simplify():Expression { return this }
}
ConstantExpr < SimpleExpr {
isConstant:Boolean = true
}
VariableExpr < SimpleExpr {
isConstant:Boolean = false
}
CompoundExpr < Expression {
operation:Token
children:Expression[]
commutesWith(op:Expression):Boolean
isCommutative:Boolean
isConstant:Boolean = (){
for each child in this.children:
if not child.isConstant, return false
return true
}
simplify():Expression {
for each child& in this.children {
child = child.simplify()
}
return this.simplify_node()
}
simplify_node(): Expression {
if this.isConstant {
evaluate this, returning new ConstExpr
} else {
if one child is simple {
if this.commutesWith(compound child)
and one grand-child doesn't match the constness of the simple child
and the other grand-child matches the constness of the simple child
{
if (compound child.isCommutative):
make odd-man-out among grand-children the outer child
rotate so that grand-children are both const or not
if grand-children are const:
set compound child to compound child.simplify_node()
}
} else {
...
}
}
return this
}
}
Например, реализация PHP для SimpleExpr и ConstantExpr может быть:
class SimpleExpr extends Expression {
public $value;
function __construct($value) {
$this->value = $value;
}
function simplify() {
return $this;
}
}
class ConstantExpr extends SimpleExpr {
// Overloading
function __get($name) {
switch ($name) {
case 'isConstant':
return True;
}
}
}
Альтернативная реализация ConstantExpr:
function Expression {
protected $_properties = array();
// Overloading
function __get($name) {
if (isset($this->_properties[$name])) {
return $this->_properties[$name];
} else {
// handle undefined property
...
}
}
...
}
class ConstantExpr extends SimpleExpr {
function __construct($value) {
parent::construct($value);
$this->_properties['isConstant'] = True;
}
}