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, ones that themselves contain no arrays. In the example, it's 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 inner 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

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