Определения

просто:

Описывает выражения без подвыражений (например, «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 , где мы возвращаем один уровень назад, восстанавливая текущий массив из «массива массива»,