Find inner arrays in nested arrays

Question

I have a nested array in 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?

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

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.

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.

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()?

Answer 1

RecursiveIteratorIterator knows the current depth of any children. As you're interested only in children that have children, filter those with no children out and look for max-depth.

Then filter again based by depth for max-depth:

$ritit = new RecursiveIteratorIterator(new RecursiveArrayIterator($arr), RecursiveIteratorIterator::SELF_FIRST);

$cf = new ChildrenFilter($ritit);

$maxdepth = NULL;
foreach($cf as $v)
{
    $maxdepth = max($maxdepth, $cf->getDepth());
}

if (NULL === $maxdepth)
{
    throw new Exception('No children found.');
}

$df = new DepthFilter($cf, $maxdepth);

foreach($df as $v)
{
    echo "Array with highest depth:\n", var_dump($v), "\n";
}

Demo / Source

Answer 2

Please, try the following code and let me know the results.

You just need to pass your array to the find_deepest function.

function find_deepest( $array )
{
    $index       = '';        // this variable stores the current position (1.2, 1.3.2, etc.)
    $include     = true;      // this variable indicates if the current position should be added in the result or not
    $result      = array();   // this is the result of the function, containing the deepest indexes
    $array_stack = array();   // this is a STACK (or LIFO) to temporarily store the sub-arrays - see http://en.wikipedia.org/wiki/LIFO_%28computing%29
    reset( $array );          // here we make the array internal POINTER move to the first position

    // each loop interaction moves the $array internal pointer one step forward - see http://php.net/each
    // if $current value is null, we reached the end of $array; in this case, we will also continue the loop, if the stack contains more than one array
    while ( ( $current = each( $array ) ) || ( count( $array_stack ) > 1 ) )
    {
        // we are looping $array elements... if we find an array (a sub-array), then we will "enter it...
        if ( is_array( $current['value'] ) )
        {
            // update the index string
            $index .= ( empty ( $index ) ? '' : '.' ) . $current['key'];
            // we are entering a sub-array; by default, we will include it
            $include = true;
            // we will store our current $array in the stack, so we can move BACK to it later
            array_push( $array_stack, $array );
            // ATTENTION! Here we CHANGE the $array we are looping; here we "enter" the sub-array!
            // with the command below, we start to LOOP the sub-array (whichever level it is)
            $array = $current['value'];
        }
        // this condition means we reached the END of a sub-array (because in this case "each()" function has returned NULL)
        // we will "move out" of it; we will return to the previous level
        elseif ( empty( $current ) )
        {
            // if we reached this point and $include is still true, it means that the current array has NO sub-arrays inside it (otherwise, $include would be false, due to the following lines)
            if ( $include )
                $result[] = $index;
            // ATTENTION! With the command below, we RESTORE $array to its precedent level... we entered a sub-array before, now we are goin OUT the sub-array and returning to the previous level, where the interrupted loop will continue
            $array = array_pop( $array_stack );
            // doing the same thing with the $index string (returning one level UP)
            $index = substr( $index, 0, strrpos( $index, '.' ) );
            // if we are RETURNING one level up, so we do NOT want the precedent array to be included in the results... do we?
            $include = false;
        }
        // try removing the comment from the following two lines! you will see the array contents, because we always enter this "else" if we are not entering a sub-array or moving out of it
        // else
        //   echo $index . ' => ' . $current['value'] . '<br>';
    }
    return $result;
}

$result = find_deepest( $my_array );
print_r( $result );

The most important parts of the code are:

1. the each command inside the while loop
2. the array_push function call, where we store the current array in the "array stack" in order to return back to it later
3. the array_pop function call, where we return one level back by restoring the current array from the "array stack"

Answer 3

Recursive foreach function, from comments at: http://php.net/manual/en/control-structures.foreach.php

/* Grab any values from a multidimensional array using infinite recursion.  --Kris */
function RecurseArray($inarray, $result) {
    foreach ($inarray as $inkey => $inval) {
        if (is_array($inval)) {
            $result = RecurseArray($inval, $result);
        } else {
            $result[] = $inval;
        }
    }

    return $result;
}

Note that the above implementation produces a flattened array. To preserve nesting:

function RecurseArray($inarray) {
    $result = array();
    foreach ( $inarray as $inkey => $inval ) {
        if ( is_array($inval) ) {
            $result[] = RecurseArray($inval);
        } else {
            // process $inval, store in result array
            $result[] = $inval;
        }
    }

    return $result;
}

To modify an array in-place:

function RecurseArray(&$inarray) {
    foreach ( $inarray as $inkey => &$inval ) {
        if ( is_array($inval) ) {
            RecurseArray($inval);
        } else {
            // process $inval
            ...
        }
    }
}

Answer 4

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 and 7 are always outer nodes. 6 is outer relative to 5, but inner relative to 1.

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

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

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;

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

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
   

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

The PHP implementation for SimpleExpr and ConstantExpr, for example, could be:

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

An alternate implementation of 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;
    }
}