Найти внутренние массивы в вложенных массивах

У меня есть вложенный массив в 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 и добавляет «.». и идентификатор массива. Таким образом, в массиве example мы получим:

 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

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-арные узлы, то 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 ) ) ) ) 

Затем вы должны написать рекурсивную функцию пост-ордера, которая упростит узлы. «Post-order» означает, что обработка узлов происходит после обработки его дочерних элементов; есть также предварительный порядок (обработать узел перед его дочерними элементами) и упорядочить (обрабатывать некоторые дочерние элементы перед узлом, а остальные – после). Далее следует грубая схема. В нем «вещь: Тип» означает «вещь» имеет тип «Тип», а «&» означает «проход по ссылке».

 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. Если внутренний великий ребенок не соответствует конституционности другого ребенка, но его брат, поменяйте братьев и сестер. Другими словами, сделайте странный внешний узел. Этот шаг готовится к следующему.
         + + + +
        / \ / \ / \ / \
       \ + 2 ---> + 2 + y ---> + y
      / \ / \ / \ / \
     1 xx 1 x 1 1 x
    
  2. Если узел и ребенок являются одной и той же коммутативной операцией, узлы могут быть перегруппированы. Например, есть поворот:

         + +
        / \ / \
       \ + c ---> a +
      / \ / \
     Аббв
    

    Это соответствует изменению «(a + b) + c» на «a + (b + c)». Вы захотите повернуть, когда «a» не соответствует константе «b» и «c». Это позволяет применить следующее преобразование к дереву. Например, этот шаг преобразует «(x + 3) +1» в «x + (3 + 1)», поэтому следующий шаг затем может преобразовать его в «x + 4».

    Общая цель состоит в том, чтобы создать дерево с детьми-соседами как братьями и сестрами. Если коммутативный узел имеет двух потомков констант, их можно вращать рядом друг с другом. Если узел имеет только один из потомков const, сделайте его дочерним, так что узел, расположенный дальше в иерархии, потенциально может объединить узел const с другим дочерним элементом const (например, const const float up, пока они не являются братьями и сестрами, они объединяются, как пузырьки в газировке).

  3. Если все дети являются постоянными, оцените узел и замените его на результат.

Обработка узлов с несколькими дочерними и дочерними узлами, оставшимися в качестве упражнений для читателя.

Объектно-ориентированная альтернатива

Использование OO-подхода (использование объектов, а не массивов для построения деревьев выражений) имеет ряд преимуществ. Операции будут более тесно связаны с узлами, для одного; они были бы свойством узлового объекта, а не как ключ узла. Также было бы проще связать вспомогательные данные с узлами выражения, что было бы полезно для оптимизации. Вам, вероятно, не нужно слишком углубляться в парадигму ООП для ее реализации. Для работы можно было создать следующую иерархию типов:

                    выражение
                   / \
         SimpleExpr CompoundExpr
         / \
 ConstantExpr VariableExpr

Существующие свободные функции, управляющие деревьями, станут методами. Интерфейсы могут выглядеть примерно как следующий псевдокод. В этом:

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

RecursiveIteratorIterator знает текущую глубину любых детей. Поскольку вас интересуют только дети, у которых есть дети, отфильтруйте их без детей и найдите максимальную глубину.

Затем снова фильтруйте по глубине для максимальной глубины:

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

Демо / источник

Рекурсивная функция foreach, начиная с комментариев по адресу: 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; } 

Обратите внимание, что приведенная выше реализация создает сплющенный массив. Чтобы сохранить вложенность:

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

Чтобы изменить массив на месте:

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

Пожалуйста, попробуйте следующий код и дайте мне знать результаты.

Вам просто нужно передать свой массив функции find_deepest .

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

Наиболее важными частями кода являются:

  1. each команда внутри цикла while
  2. array_push функции array_push , где мы храним текущий массив в «стеке массива», чтобы вернуться к нему позже
  3. array_pop функции array_pop , где мы возвращаем один уровень назад, восстанавливая текущий массив из «массива массива»,