定义
- simple:
- Describes expressions without sub-expressions (e.g. "5", "x").
- compound:
- Describes expressions that have sub-expressions (e.g. "3+x", "1+2").
- constness:
- Whether an expression has a constant value (e.g. "5", "1+2") or not (e.g. "x", "3+x").
- outer node:
- In an expression tree, a node reachable by always traversing left or always traversing right. "Outer" is always relative to a given node; a node might be "outer" relative to one node, but "inner" relative to that node's parent.
- inner node:
- In an expression tree, a node that isn't an outer node.
有关“内部”和“外部”节点的说明，请考虑：
__1__
/ \
2 5
/ \ / \
3 4 6 7
3 and 7 are always outer nodes. 6 is outer relative to 5, but inner relative to 1.
Answer
这里的困难更多地在于表达格式的不均匀而不是嵌套。如果您使用表达式树，则示例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
) ) ) )
然后，您将编写一个后序递归函数来简化节点。 “后序”是指节点处理发生在处理其子节点之后；还有预序（在其子节点之前处理节点）和中序（在节点之前处理一些子节点，在节点之后处理其余节点）。以下是一个粗略的轮廓。其中，“thing : Type”表示“thing”具有类型“Type”，“&”表示按引用传递。
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 节点与祖先的另一个 const 子节点组合起来（即 const 节点向上浮动，直到它们成为兄弟节点，此时它们像苏打水中的气泡一样结合在一起）。
- 如果所有子节点都是常数，则评估该节点并将其替换为结果。
