查找嵌套数组的数组内 [英] Find inner arrays in nested arrays

问题描述

我在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' => ")"
       )
);       

我要在这里处理的最里面的阵列，一个与评论：我想找到这一个。是否有一个功能是什么？

I need to process the innermost arrays here, the one with the comment: "I want to find this one." Is there a function for that?

我也想过做（写成一个想法，而不是正确的PHP）：

I have thought about doing (written as an idea, not as correct 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;
            }
        }
    }
}

那么，它的作用是它让 $名称数组中的当前关键。如果该值是一个数组，它进入它用foreach，并增加了。和该阵列的ID。所以我们的例子中数组中结束：

So what it does is it makes $name the current key in the array. If the value is an array, it goes into it with foreach and adds "." and the id of the array. So we would in the example array end up with:

array (
    '0' => "1.3.2",
)

然后我可以处理这些值来访问肠子阵列。

Then I can process those values to access the innner arrays.

问题是，我想找到的内阵列的阵列是动态的，并取得了用户的输入。 （这将输入字符串，其中发现+或 - ，如果它包含括号把它在一个单独的嵌套数组因此，如果用户类型很多括号之内，就会有大量的嵌套数组。）
因此，我需要为20倍，这种模式走下来，仍然只会赶上20嵌套数组不管是什么。

The problem is that the array that I'm trying to find the inner arrays of is dynamic and made of a user input. (It splits an input string where it finds + or -, and puts it in a separate nested array if it contains brackets. So if the user types a lot of brackets, there will be a lot of nested arrays.) Therefore I need to make this pattern go for 20 times down, and still it will only catch 20 nested arrays no matter what.

是否有一个函数，再？还是有办法使它做到这一点没有我的code吗？也许让一个循环做的foreach模式的必要数量，并通过评估运行（）？

Is there a function for that, again? Or is there a way to make it do this without my long code? Maybe make a loop make the necessary number of the foreach pattern and run it through eval()?

推荐答案

有关的内部和外部的节点说明，考虑：

Definitions

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.

For an illustration of "inner" and "outer" nodes, consider:

       __1__
      /     \ 
     2       5
    / \     / \
   3   4   6   7

3和7总是外的节点。 6是相对于外到5，但相对于1内。

3 and 7 are always outer nodes. 6 is outer relative to 5, but inner relative to 1.

的难点在于这里更比嵌套的前pression格式参差不齐。如果使用前pression树的例子 5倍+ 3 =（X +（3+（5-3）））方程的解析为：

The difficulty here lies more in the uneven expression format than the nesting. If you use expression trees, the example 5x+3=(x+(3+(5-3))) equation would parse to:

array(
    '=' => array(
        '+' => array( // 5x + 3
            '*' => array(
                5, 'x'
            ),
            3
        )
        '+' => array( // (x+(3+(5-3)))
            'x',
            '+' => array( // (3+(5-3))
                3,
                '-' => array(
                    5, 3
)   )   )   )   )

请注意，对于二进制运算节点是二进制的，和一元行动将有一元的节点。如果二元交换操作的节点可以合并为n元节点， 5倍+ 3 = X + 3 + 5-3 可以解析为：

Note that nodes for binary operations are binary, and unary operations would have unary nodes. If the nodes for binary commutative operations could be combined into n-ary nodes, 5x+3=x+3+5-3 could be parsed to:

array(
    '=' => array(
        '+' => array( // 5x + 3
            '*' => array(
                5, 'x'
            ),
            3
        )
        '+' => array( // x+3+5-3
            'x',
            3,
            '-' => array(
                5, 3
)   )   )   )

然后，你会写一个后序的递归函数，将简化节点。 后序是指其处理后的孩子节点处理情况;这里还有pre级（处理其子节点之前）和顺序（过程节点之前的一些孩子，之后的其余部分）。下面是一个大致的轮廓。在这里面，事：输入是指东西的类型是类型和＆安培;表示传递通过引用。

Then, you'd write a post-order recursive function that would simplify nodes. "Post-order" means node processing happens after processing its children; there's also pre-order (process a node before its children) and in-order (process some children before a node, and the rest after). What follows is a rough outline. In it, "thing : Type" means "thing" has type "Type", and "&" indicates 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 。它可以对前pression节点执行一系列操作：

In a way, the real challenge is writing simplify_node. It could perform a number of operations on expression nodes:

1. 如果内盛大的孩子不符合其他孩子的常量性，但其兄弟呢，交换的兄弟姐妹。换句话说，使奇数人出的外节点。这一步骤是在preparation为下。
   

1. If an inner grand-child doesn't match the constness of the other child but its sibling does, swap the siblings. In other words, make the odd-man-out an outer node. This step is in preparation for the next.

    +            +                +            +
   / \          / \              / \          / \
  +   2  --->  +   2            +   y  --->  +   y
 / \          / \              / \          / \
1   x        x   1            x   1        1   x

如果一个节点和一个子是相同的可交换操作中，节点可以被重新排列。例如，有旋转：

If a node and a child are the same commutative operation, the nodes could be rearranged. For example, there's rotation:

    +            +
   / \          / \
  \+   c  --->  a   +
 / \              / \
a   b            b   c

此对应改变（A + B）+ C至A +（B + C）。你想旋转时一个不匹配B和C的常量性。它允许下变换被应用到树中。例如，该步骤将转换成（X + 3）+ 1到X +（3 + 1），所以下一步然后可以将其转换为X + 4。

This corresponds to changing "(a+b)+c" to "a+(b+c)". You'll want to rotate when "a" doesn't match the constness of "b" and "c". It allows the next transformation to be applied to the tree. For example, this step would convert "(x+3)+1" to "x+(3+1)", so the next step could then convert it to "x+4".

总体目标是使树常量儿童兄弟姐妹。如果一个交换节点有两个常量后代，它们可以彼此相邻地旋转。如果一个节点只有一个常量后代，使它成为一个子使得节点进一步向上在层次结构可以潜在地与另一祖先的常量儿童结合常量节点（即常量节点上浮，直到他们的兄弟姐妹，在该点他们结合就像苏打气泡）。

The overall goal is to make a tree with const children as siblings. If a commutative node has two const descendants, they can be rotated next to each other. If a node has only one const descendent, make it a child so that a node further up in the hierarchy can potentially combine the const node with another of the ancestor's const children (i.e. const nodes float up until they're siblings, at which point they combine like bubbles in soda).

与一个以上的化合物的儿童和n进制节点处理节点留下作为练习读者

Handling nodes with more than one compound child and n-ary nodes left as exercises for the reader.

这是面向对象的方法（使用对象，而不是阵列构建前pression树）将具有许多优点。操作将与节点更紧密地相关联，对于一个;他们会是一个节点对象的属性，而不是作为节点的关键。它也将是容易与前pression节点，这将是对优化有用的辅助数据相关联。你可能不会需要太深入OOP范式实现这一点。下面这个简单的类型层次结构可以工作进行：

An OO approach (using objects rather than arrays to build expression trees) would have a number of advantages. Operations would be more closely associated with nodes, for one; they'd be a property of a node object, rather than as the node key. It would also be easier to associate ancillary data with expression nodes, which would be useful for optimizations. You probably wouldn't need to get too deep into the OOP paradigm to implement this. The following simple type hierarchy could be made to work:

                   Expression
                  /          \
        SimpleExpr            CompoundExpr
        /        \
ConstantExpr    VariableExpr

现有操纵树将成为免费的方法的功能。该接口可能看起来像下面的伪code。在它：

Existing free functions that manipulate trees would become methods. The interfaces could look something like the following pseudocode. In it:

• 子＆lt;父的意思是孩子是父的子类。


• 属性（如 isConstant ）即可方法或字段;在PHP中，你可以通过实现这个超载。


• （...）{...} 显示功能，带括号的参数和支架（很像功能的主体（ ...）{...} 在Javascript）。此语法用于那些方法的属性。普通的方法简单地使用括号内为方法体。

• Child < Parent means "Child" is a subclass of "Parent".
• Properties (such as isConstant) can be methods or fields; in PHP, you can implement this using overloading.
• (...){...} indicate functions, with the parameters between parentheses and the body between brackets (much like function (...){...} in Javascript). This syntax is used for properties that are methods. Plain methods simply use brackets for the method body.

现在的样本：

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;
    }
}

这篇关于查找嵌套数组的数组内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！