Обратная польская запись

@Александр30 · Регистрация: 06.06.2013

Подскажите, как по обратной польской записи выражения построить дерево выражения

Например:
дана запись 1 2 + 3 4 * -

выход:
дерево

@Issues · 12.07.2013, 00:45

http://habrahabr.ru/post/100869/

Добавлено через 5 минут
Обратная польская запись
Перевод инфиксного выражения в постфиксное (обратная польская запись)
Задача "Калькулятор"

@ya_noob · 12.07.2013, 10:27

Сообщение от Александр30

Подскажите, как по обратной польской записи выражения построить дерево выражения

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

Алгоритм тривиален:
(вариант №1: идем по выражению слева направо)
1. восстанавливаем левое поддерево (рекурсия)
2. восстанавливаем правое поддерево (рекурсия)
3. вытаскиваем из обхода корень дерева (т.е. знак операции)
4. соединяем его с найденными поддеревьями.

(вариант №2: идем по выражению справа налево)
1. вытаскиваем из обхода корень дерева (знак операции)
2. восстанавливаем правое поддерево (рекурсия)
3. восстанавливаем левое поддерево (рекурсия)
4. соединяем потомков с корнем.

Но над реализацией надо немного подумать (я не указал когда вытаскиваются числа из обхода). Думайте.

@Александр30 0 / 0 / 0 Регистрация: 06.06.2013 Сообщений: 14
		1
	Обратная польская запись 12.07.2013, 00:11. Просмотров 4212. Ответов 2 Метки нет (Все метки) Подскажите, как по обратной польской записи выражения построить дерево выражения Например: дана запись 1 2 + 3 4 * - выход: дерево 0 Изображения

@Issues 433 / 368 / 149 Регистрация: 06.08.2012 Сообщений: 961
	12.07.2013, 00:45	2
	http://habrahabr.ru/post/100869/ Добавлено через 5 минут Обратная польская запись Перевод инфиксного выражения в постфиксное (обратная польская запись) Задача "Калькулятор" 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	12.07.2013, 10:27	3
	Сообщение от Александр30 Подскажите, как по обратной польской записи выражения построить дерево выражения Переформулирую: как, зная обход бинарного дерева в обратном порядке (левый-правый-корень), восстановить это дерево. Алгоритм тривиален: (вариант №1: идем по выражению слева направо) 1. восстанавливаем левое поддерево (рекурсия) 2. восстанавливаем правое поддерево (рекурсия) 3. вытаскиваем из обхода корень дерева (т.е. знак операции) 4. соединяем его с найденными поддеревьями. (вариант №2: идем по выражению справа налево) 1. вытаскиваем из обхода корень дерева (знак операции) 2. восстанавливаем правое поддерево (рекурсия) 3. восстанавливаем левое поддерево (рекурсия) 4. соединяем потомков с корнем. Но над реализацией надо немного подумать (я не указал когда вытаскиваются числа из обхода). Думайте. 1

Опции темы