рекурсия, как отдать путь до найденного массива во вне

predator

web designer
я вижу естественное решение маленьким конечным автоматом (или 2мя) в 1 проход
объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?
лучше всего мелкий пример
 

fixxxer

К.О.
Партнер клуба
охоспади

какие евалы? какая рекурсия?

PHP:
<?php

function getNestedArrayElementByPath(array $data, array $path) {
    $ptr = &$data;
    foreach ($path as $element) {
        if (is_array($ptr) && isset($ptr[$element])) {
            $ptr = &$ptr[$element];
        } else {
            return false;
        }
    }
    return $ptr;
}

$data = array(
    'a' => array(
        'b' => array(
            'c' => array(
                'd' => array(
                    'e' => 'test'
                )
            )
        )
    )
);

$path = array('a', 'b', 'c', 'd', 'e');

var_dump(getNestedArrayElementByPath($data, $path));
 

AmdY

Пью пиво
Команда форума
fixxxer
ну вот, пришёл и всё испортил. у меня есть похожая функция, но вот откуда-то у меня сильная нелюбовь к ссылкам не знаю, срочно нужно поправить.
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?
лучше всего мелкий пример
что именно объяснить - как автоматом парсить строку?
читаешь статью
как создавать вложенные структуры?
читаешь про массивы
тебе автомат написать?
а контрольную по вышке тебе не решить?
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
>откуда-то у меня сильная нелюбовь к ссылкам
когда-то их юзали везде и не к месту,
"$ptr = &$ptr[$element];" с простым присваиванием будет работать точно так же, учитывая ссылочную природу переменных
 

predator

web designer
всем спасибо за внимание и участие ))
вот что получилось:
1) Конечный автомат
PHP:
/**
 * Парсинг конструкций аля '{dog|cat} the {food {in|out} the air {some|more|hm}} i liked {car|bike|u-bann}'
 * на основе конечных машин (Finite State Machine)
 *
 * @category Project
 * @package Project_Articles
 * @license http://opensource.org/licenses/ MIT License
 */
class Project_Articles_Rewrite_FSM {

	private $_content=''; // Буфер данных
	private $_intLength=0; // Длина буфера
	private $_intPos=0; // Позиция курсора в буфере

	private $_line=0;
	private $_column=0;

	private $_error='';

	// Остальные символы имеют код 1
	private $_inState=array(
		'{'=>2, // начало вариантов
		'}'=>4, // конец варианта и выход из рекурсии
		'|'=>3, // конец варианта
		null=>4 // конец символов - аналогичен концу варианта, только в данном случае вариантом считается сам текст
	);

	private $_parserAutomat=array(
		/*
		-1 ошибка
		0 начало разбора - ожидаем символ или левую скобку
		1 получили символ, накапливаем их - ожидаем всё что угодно
		2 получили {. идём в рекурсию - после ожидаем символ или ещё одну левую скобку
		3 получили |. разбираемся с вариантом - ожидаем символ, любую скобку
		4 получили }. разбираемся с вариантом и выходим из рекурсии - ожидаем всё что угодно
		*/
		// состоян 0, 1, 2, 3, 4
		'1'=>array( 1, 1, 1, 1, 1 ), // символ
		'2'=>array( 2, 2, 2, 2, 2 ), // левая скобка
		'3'=>array(-1,3,-1,-1, 3 ), // палка
		'4'=>array(-1, 4,-1,4, 4 ), // правая скобка или конец строки
	);
	private $_state=0;

	public function setData( $_str='' ) {
		$this->_content=$_str;
		$this->_intLength=strlen( $_str );
		return $this;
	}

	public function getError() {
		return $this->_error;
	}

	private function updateStaying() {
		if ( $this->_content[$this->_intPos]=="\n" ) {
			$this->_line++;
			$this->_column=0;
		} else {
			$this->_column++;
		}
	}

	private function scan() {
		while ( $this->_intPos<$this->_intLength ) {
			$symbol=$this->_content[$this->_intPos];
			$this->updateStaying();
			$this->_intPos++;
			return $symbol;
		}
		return null;
	}

	public function parse() {
		$_arrVariation=array();
		$_arrVariants=array();
		$_strCurentVariant='';
		while( 1 ) {
			$symbol=$this->scan(); // получаем символ от сканера
			$instate=isSet( $this->_inState[$symbol] ) ?$this->_inState[$symbol]:1; // Устанавливаем код, подаваемого на вход автомата, символа
			$prev=$this->_state;
			$this->_state=$this->_parserAutomat[$instate][$this->_state];
			switch( $this->_state ) {
				case 1: // получили символ, накапливаем их - ожидаем всё что угодно
					$_strCurentVariant.=$symbol;
				break;
				case 2: // получили {. идём в рекурсию - после ожидаем символ или ещё одну левую скобку
					$_strCurentVariant.='%s';
					$_arrVariation[]=$this->parse();
				break;
				case 3: // получили |. разбираемся с вариантом - ожидаем символ, любую скобку
					if ( !empty( $_arrVariation ) ) {
						$_arrGenerated=$this->everyPossibleVariants( $_strCurentVariant, $_arrVariation );
						$_arrVariants=array_merge( $_arrVariants, $_arrGenerated );
						$_arrVariation=array();
					} else {
						$_arrVariants[]=$_strCurentVariant;
					}
					$_strCurentVariant='';
				break;
				case 4: // получили }. разбираемся с вариантом и выходим из рекурсии - ожидаем всё что угодно
					if ( !empty( $_arrVariation ) ) {
						$_arrGenerated=$this->everyPossibleVariants( $_strCurentVariant, $_arrVariation );
						$_arrVariants=array_merge( $_arrVariants, $_arrGenerated );
					} else {
						$_arrVariants[]=$_strCurentVariant;
					}
					return $_arrVariants;
				break;
				default: throw new Exception( Core_Errors::DEV.'|line: '.$this->_line.', col: '.$this->_column.' in "'.$this->_content.'"' ); break 2;
			}
		}
		return array();
	}

	private function everyPossibleVariants( $_str='', $_arr=array() ) {
		$f=new Core_Math_Combiner();
		$f->setData( $_arr );
		foreach($f as $e) {
			$arrRes[]=vsprintf( $_str, $e );
		}
		return $arrRes;
	}
}
1) Комбинаторика
PHP:
/**
 * Комбинирование массивов для получения всех возможных комбинаций
 * в порядке поступления массивов
 * т.е. напрмер array( array( dog, cat ), array( food, tooth ) ) преобразуются в 
 * dog food
 * dog tooth
 * cat food
 * cat tooth
 *
 * @category Core
 * @package Core_Math
 * @copyright Copyright (c) 2005-2010, Rodion Konnov
 * @license http://opensource.org/licenses/ MIT License
 */
class Core_Math_Combiner implements Iterator {
	protected $data=null; // масси массивов
	protected $limit=null; // количество возможных комбинаций (|arr1|*|arr2|...*|arrN|)
	protected $current=null;

	public function __construct() {
		$this->setData( func_get_args() );
	}

	public function setData( $_arr=array() ) {
		$this->data=array_reverse( $_arr );
		$this->init();
	}

	private function init() {
		$this->rewind();
		$this->limit=array_product(array_map('count', $this->data));
	}

	public function current() {
		/* this works like a baseX->baseY converter (e.g. dechex() )
		   the only difference is that each "position" has its own number of elements/"digits"
		*/
		// <-- add: test this->valid() -->
		$rv=array();
		$key=$this->current;
		foreach( $this->data as $e) {
			array_unshift( $rv, $e[$key % count($e)] );
			$key=(int)($key/count($e));
		}
		return $rv;
	}

	public function key() { return $this->current; }
	public function next() { ++$this->current; }
	public function rewind () { $this->current=0; }
	public function valid () { return $this->current < $this->limit; }
}
1) Использование
PHP:
$fsm=new Project_Articles_Rewrite_FSM();
$_arrVariants=$fsm->setData( '{dog|cat} the {food {in|out} the air {some|more|hm}|test} i liked {car|bike|u-bann}' )->parse();
тему можно закрывать, или давайте поговорим об этом )
 

predator

web designer
ещё можно присовокупить защиту vsprintf от имеющихся в тексте знаков процента - %
для всего текста вначале их надо удвоить, а когда получили конец текста при разборе
после генерации конечных вариантов надо заменять взяд %% на %
как-то так
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
сразу видно: будущий Герой Дебага

автоматы и так трудно дебажить, а с рекурсией - это офигеть
зачем решать сложную задачу сложным алгоритмом?
надо решить ее очень сложным алгоритмом с непредсказуемым поведением :)
 

predator

web designer
я знаю что любую рекурсию можно вывернуть в итерацию
но примеров конкретных пока не видел

если у вас есть мысли по этому поводу
я буду рад их услышать
 

tz-lom

Продвинутый новичок
predator
не любую рекурсию можно превратить в итерацию
пример превращения:
PHP:
function fact($n)
{
if($n>1)return $n*fact($n-1);
else return 1;
}

function nfact($n)
{
$res = 1;
while($n>1){$res*=$n--;}
return $res;
}
и пример невозможности:
PHP:
function fuuuuuuuu($n)
{
if($n>1)return $n*fuuuuuuuu($n); //stack will die here
else return 1;
}
 

флоппик

promotor fidei
Команда форума
Партнер клуба
Почему это второй пример нельзя вывернуть в итерацию?
PHP:
function fuu ($n)
{
  if ($n <= 1) return  1;
  $serult = 1;
  while (true)
  {
    $result = $result * $n;
  }
}
Просто сама рекурсия в твоем примере бесконечна и бессмысленна.
 

tz-lom

Продвинутый новичок
флоппик,это был тонкий юмор над математиками,которые такими вещями не брезгуют
любую вменяемую рекурсию можно записать как цикл над FIFO хранящем параметры и результат
другое дело что говорить мол рекурсия плохо,надо избегать я бы не стал,есть очень изящные и понятные решения с рекурсией в главной роли
 

флоппик

promotor fidei
Команда форума
Партнер клуба
«Плохо - хорошо» это не та категория, которой можно измерять алгоритмы. Рекурсия требует больше ресурсов на получение результата, чем линейный алгоритм, при этом выигрывая лишь в читаемости.

И не понимаю, причем тут математики.
 

tz-lom

Продвинутый новичок
флоппик
на счёт ресурсов весьма спорный вопрос,в ручную контекст исполнения хранить накладнее чем вам это сделает интерпретатор
плюс код вроде
PHP:
function rec(...){ //bunch of code
rec();
//bunch of code }
в виде итерации будет выглядеть очень неприглядно
и на самом деле отладка рекурсии ничем не отличается от отладки функции,тот же контекст исполнения,та же вариация входных параметров
 

флоппик

promotor fidei
Команда форума
Партнер клуба
флоппик
на счёт ресурсов весьма спорный вопрос
Даю наводку - стек вызовов — не резиновый. И его ресурсная "стоимость" значительно выше, чем затраты на память.

Я помню, как мой препод в свое время (лет 12 назад) это наглядно показал на примере турбо паскаля - факториал 6 получить рекурсивно на паскале было нельзя - стека не хватало.

Во вторых, любой рекурсивный алгоритм можно развернуть в линейный.

В третьих, "неприглядно" - тоже не показатель. Интерпретатору безразлична "красота" кода.
 

tz-lom

Продвинутый новичок
флоппик
факториал 6ти в TP7.0 это всего 5 вызовов внутри рекурсии и 1 вызов самой функции,я уверен что 7й TP это запросто сделает
ресурсная ёмкость стека НИЖЕ чем массивов,потому что его не надо аллоцировать

компу и обфусцированный код сойдёт,но таки вы его в первозданном виде возжелаете для отладки,не стоит этого забывать
 

tz-lom

Продвинутый новичок
флоппик
я к тому что "красота" и "неприглядно" можно вполне относить к критериям качества кода
 

Вурдалак

Продвинутый новичок
флоппик
факториал 6ти в TP7.0 это всего 5 вызовов внутри рекурсии и 1 вызов самой функции,я уверен что 7й TP это запросто сделает
ресурсная ёмкость стека НИЖЕ чем массивов,потому что его не надо аллоцировать

компу и обфусцированный код сойдёт,но таки вы его в первозданном виде возжелаете для отладки,не стоит этого забывать
— бред сивой кобылы.
 
Сверху