我在PHP中有一个嵌套数组:
array (
'0' => "+5x",
'1' => array (
'0' => "+",
'1' => "(",
'2' => "+3",
'3' => array (
'0' => "+",
'1' => "(",
'2' => array ( // I want to find this one.
'0' => "+",
'1' => "(",
'2' => "+5",
'3' => "-3",
'4' => ")"
),
'3' => "-3",
'4' => ")"
),
'4' => ")"
)
);
我需要在这里处理最里面的数组,一个带有注释的数组:"我想找到这个." 有功能吗？
我考虑过做(写作一个想法,而不是正确的PHP):
foreach ($array as $id => $value) {
if ($value is array) {
$name = $id;
foreach ($array[$id] as $id_2 => $value_2) {
if ($value_2 is array) {
$name .= "." . $id_2;
foreach ($array[$id][$id_2] as $id_3 => $value_3) {
if ($value_3 is array) {
$name .= "." . $id_3;
foreach ($array[$id][$id_2][$id_3] as $id_4 => $value_4) {
if ($value_4 is array) {
$name .= "." . $id_4;
foreach [and so it goes on];
} else {
$listOfInnerArrays[] = $name;
break;
}
}
} else {
$listOfInnerArrays[] = $name;
break;
}
}
} else {
$listOfInnerArrays[] = $name;
break;
}
}
}
}
它的作用是它使$name数组中的当前键.如果值是数组,则使用foreach进入数组并添加"." 和数组的id.所以我们在示例数组中最终得到:
array (
'0' => "1.3.2",
)
然后我可以处理这些值来访问内部数组.
问题是我试图找到内部数组的数组是动态的,并由用户输入组成.(它将输入字符串拆分为+或 - ,如果它包含括号,则将其放在单独的嵌套数组中.因此,如果用户键入了很多括号,则会有很多嵌套数组.)因此我需要使这个模式向下移动20次,并且无论如何它仍然只能捕获20个嵌套数组.
那还有一个功能吗？或者有没有办法让它在没有我的长代码的情况下做到这一点？也许制作一个循环来制作必要数量的foreach模式并运行它eval()？
out*_*tis 16
有关"内部"和"外部"节点的说明,请考虑:
__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-ary节点,则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","&"表示pass-by-reference.
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节点浮动直到它们是兄弟节点,此时它们像苏打水中的气泡一样结合在一起.
处理具有多个复合子节点和n-ary节点的节点作为读者的练习.
OO方法(使用对象而不是数组来构建表达式树)将具有许多优点.操作将与节点关联得更紧密; 它们是节点对象的属性,而不是节点键.将辅助数据与表达式节点相关联也会更容易,这对优化很有用.您可能不需要深入了解OOP范例来实现它.可以使用以下简单类型层次结构:
Expression
/ \
SimpleExpr CompoundExpr
/ \
ConstantExpr VariableExpr
操纵树的现有自由函数将成为方法.接口看起来像下面的伪代码.在里面:
Child < Parent 表示"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;
}
}