predator
web designer
объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?я вижу естественное решение маленьким конечным автоматом (или 2мя) в 1 проход
лучше всего мелкий пример
объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?я вижу естественное решение маленьким конечным автоматом (или 2мя) в 1 проход
<?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));
что именно объяснить - как автоматом парсить строку?объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?
лучше всего мелкий пример
/**
* Парсинг конструкций аля '{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;
}
}
/**
* Комбинирование массивов для получения всех возможных комбинаций
* в порядке поступления массивов
* т.е. напрмер 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; }
}
$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();
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;
}
function fuuuuuuuu($n)
{
if($n>1)return $n*fuuuuuuuu($n); //stack will die here
else return 1;
}
function rec(...){ //bunch of code
rec();
//bunch of code }
Даю наводку - стек вызовов — не резиновый. И его ресурсная "стоимость" значительно выше, чем затраты на память.флоппик
на счёт ресурсов весьма спорный вопрос
— бред сивой кобылы.флоппик
факториал 6ти в TP7.0 это всего 5 вызовов внутри рекурсии и 1 вызов самой функции,я уверен что 7й TP это запросто сделает
ресурсная ёмкость стека НИЖЕ чем массивов,потому что его не надо аллоцировать
компу и обфусцированный код сойдёт,но таки вы его в первозданном виде возжелаете для отладки,не стоит этого забывать