我在 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() 运行它？

最佳答案

定义

简单:

描述没有子表达式的表达式(例如“5”、“x”)。

化合物:

描述具有子表达式的表达式(例如“3+x”、“1+2”)。

常量:

表达式是否具有常量值(例如“5”、“1+2”)或不具有常量值(例如“x”、“3+x”)。

外节点:

在表达式树中，通过始终向左遍历或始终向右遍历可到达的节点。 “外部”总是相对于给定的节点；一个节点相对于一个节点可能是“外部”，但相对于该节点的父节点是“内部”。

内部节点:

在表达式树中，不是外部节点的节点。

对于“内部”和“外部”节点的说明，请考虑:

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

Answer

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 元节点，则 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。它可以在表达式节点上执行许多操作:

1. 如果一个内孙子的常量​​性与另一个 child 的常量性不匹配但它的 sibling 匹配，则交换 sibling 。换句话说，使奇人出局成为外部节点。这一步是为下一步做准备。

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

2. 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
   

   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).

3. If all children are constant, evaluate the node and replace it with the result.

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

Object-Oriented Alternative

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

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

• 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.

Now for the sample:

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

例如，SimpleExpr 和 ConstantExpr 的 PHP 实现可以是:

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

关于php - 如何在嵌套数组中查找叶数组？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8197469/