Построение дерева по префиксной записи

Seregarival

Новичок
Построение дерева по префиксной записи

Написал 2 скрипта по переводу арифметического выражения в префиксную и постфиксную запись.
Теперь задача стоит - построить дерево арифметического разбора.
Решил строить по префиксной записи. Пример:
(a+b)*(c-d) префиксная запись: *+ab-cd

Подскажите пожалуйста, какую структуру лучше использовать, чтобы отобразить дерево? Видел, что есть CDBTree, Nested Sets, Materialized Paths ... Говорят проще всего использовать Java, но я его не знаю вообще...

Какую на ваш взгляд реализацию лучше выбрать?
 

Вурдалак

Продвинутый новичок
Чтобы отобразить дерево, не требуется ничего из перечисленного.
 

Seregarival

Новичок
Простите, его еще создать надо... алгоритм мне понятен, то есть какое число поместить в корень, какие будут поддеревьями понятно, а вот в какую структуру их помещать, чтоб потом не сложно было вывести ... это задачка для меня! Подскажите пожалуйста, чтоб я не изобретал велосипед, я не прошу написать код, мне бы хотя бы наводящую подсказочку, с чем работать :))
 

Вурдалак

Продвинутый новичок
Автор оригинала: Seregarival
Простите, его еще создать надо
— создавать ничего не надо, потому что само по себе выражение «* + a b - c d» уже, в принципе, является своеобразным представлением дерева. Ты его хочешь перевести в другую форму — nested sets или adjacency list. Смысла-то немного.

Гораздо сложнее красиво отобразить это дерево. Можно на картинке. Можно через HTML-таблицы. Ещё как-то...
 

fixxxer

К.О.
Партнер клуба
http://dimants.ru/archives/64

нашел в гугле за примерно 30 секунд

не тому вас учат =)
 

Seregarival

Новичок
fixxxer, это не лабораторная работа, я готовую не искал, учусь работать с PHP, по-тихоньку готовлюсь к диплому ...

Идея насчет массива заинтересовала, но что-то всё не могу сообразить, как это реализовать ...
Например: Читаем первый символ - операция - создаем массив:

$array['Tree']=array('$simbol', 'Left', 'Right')
Далее читаем остальные символы
Операция:
$array['$simbol']=array('$simbol', 'Left'=>array('$newsimbol', 'Left', 'Right'), 'Right');
Операнд:
$array['$simbol']=array('$simbol', 'Left'=>'$newsimbol', 'Right');

Непонятно как в этом случае организовать поиск места вставки очередного элемента. Посоветуйте пожалуйста что-нибудь.
 

Fortop

Новичок
Непонятно как в этом случае организовать поиск места вставки очередного элемента
зачем его искать?
нарисуй свое дерево и увидишь каким должен быть массив

например
PHP:
array(
оператор1 =>
    array(
        параметр1,
        оператор1 => array(
            параметр2,
            параметр3)
        )
)
При рекурсивных разборах такие деревяшки чуть ли не сами-собой получаются.

При нерекурсивных у тебя есть стек и используешь последний узел из него, в который(узел) ты и вставляешь ветку.
Как ветка закончена, мы выталкиваем узел из стека.
 

Seregarival

Новичок
С рекурсией так и не разобрался ... к сожалению :(
Не знаю как создать дерево автоматически. Решил разобрать хотя бы вручную...
PHP:
<?php
Function Tree($formula)
	{
		$new='';
		$formula = str_replace(" ","", $formula);
			$dl=strlen($formula);
			for ($i = 0; $i <= $dl-1; $i++)
			{
				$simbol=substr($formula,$i,1);
				switch($simbol)
				{
					case "+": case "-": case "*": case "/":
						$list[$i+1]=$simbol;
						$simbol1='t';
						$new=$new.$simbol1;
						break;
					case "a": case "b": case "c": case "d": case "e": case "f":
						$list[$i+1]=$simbol;
						$simbol1='a';
						$new=$new.$simbol1;
						break ;	
				}
			}
			print($new);
			if ($new == 'ttaatataa')
				{
$arrays=array($list[1]=>array($list[2]=>array($list[3], $list[4])), $list[5]=>array($list[6], $list[7]=>array($list[8], $list[9])) );
				} 
			if ($new == 'tattataaa')
				{
$arrays=array($list[1]=>array($list[2], $list[3]=>array($list[4]=>array($list[5], $list[6]=>array($list[7], $list[8])), $list[9])) );
				} 	
				$output=print_r($arrays, true);
				print $output;
	}
$formula='-a+/b/cde';	
print('<br>');	
print('Дерево: <br>');
Tree($formula);
?>
Вывод дерева получается в таком виде:
Array ( [-] => Array ( [0] => a [+] => Array ( [/] => Array ( [0] => b [/] => Array ( [0] => c [1] => d ) ) [0] => e ) ) )
Подскажите пожалуйста, а как можно сделать, чтобы оно хоть немного на дерево было похоже?
 

Seregarival

Новичок
$output=print_r($arrays, true);
print $output;

У меня так и сделано за исключением <pre> только на дерево не очень смахивает... Можно как-нибудь убрать надписи Array и разделить его на несколько строчек, чтоб хоть вид дерева был, а не строки со значениями ... ?
 

Seregarival

Новичок
Ответьте пожалуйста кто знает на вопросик:
Есть 2 PHP скрипта в разных файлах: мне нужно чтоб скрипт treeple.php получал значение переменной $formul из файла prefix.php

У меня в файле prefix.php идет вызов:
include 'treeple.php';


Знаю, что GET или POST еолько на деле ничего не выходит ...
 

Seregarival

Новичок
<form method="POST" action="form_handler.php">
Введите Ваше имя: <input type="text" name="name">
<br>
<input type="submit" name="okbutton" value="OK">
</form>

<?
echo "<h1>Привет, <b>" . $_POST['name'] . "</b></h1>!";
?>


Я читал уже эти FAQи )) С кнопки я тоже могу по примеру выбрать значение, а вот как переменную забрать ...
То есть во всех примерах POST в свойствах кнопки, а где его поместить в простом файле...
 

dimagolov

Новичок
Seregarival, ты не объяснил главного. что из себя представляют файлы treeple.php и prefix.php и как они связаны. была надежда, что до тебя это дойдет после прочтения ссылки.
 

Seregarival

Новичок
В файле prefix.php строится префиксная запись выражения, она хранится в переменной $formul. Мне нужно чтобы файл treeple.php взял это значение $formul и начал работать с ним ...
 
Сверху