Решение примера в обратной польской нотации

21.01.2011 | Категория: Web-мастеру и не только | Автор: ManHunter

Обратная польская нотация - один из классических алгоритмов, используемых в вычислительной технике. Он используется для вычислений, и особенностью является следование символов операций за символами операндов, а также в отсутствии скобок. Если интересно, можете почитать описание алгоритма польской нотации. Листая сайт с вакансиями, я наткнулся на одно предложение работы, где в качестве тестового задания требовалось написать функцию, которая получает строку примера, записанного в обратной польской нотации, и возвращает результат вычислений. Сама вакансия для меня никакого интереса не представляла, с работой у меня все в порядке, а задание показалось интересным. Вот что у меня сперва получилось.

Code (PHP) : Убрать нумерацию

// Польская нотация. Реализация алгоритма с рекурсией
function polish_recursive($str) {
// подчистить строку и разделить ее на "стек"
$stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
$cnt=count($stack);
// если в стеке более 1 элемента
if ($cnt>1) {
// debug
//echo join(' ',$stack).'<br>';
// пройтись по стеку
for ($i=0; $i<$cnt; $i++) {
// знак арифметического действия?
if (in_array($stack[$i], array('-', '+', '*', '/'))) {
// слева осталось меньше двух цифр?
if ($i<2) { return 'error'; }
// выполнить операцию, записать в "стек" результат
eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
// изъять из "стека" операнды
unset($stack[($i-1)]);
unset($stack[($i-2)]);
break;
}
else {
// не арифметический знак и не число
if (!is_numeric($stack[$i])) { return 'error'; }
}
}
// в стеке ничего не изменилось после выполнения цикла
if ($cnt==count($stack)) { return 'error'; }
// следующий рекурсивный проход
$str=polish_recursive(join(' ',$stack));
}
// результат
return($str);
}

В решении реализован псевдо-стек в массиве, а вычисление выполняется рекурсивно до получения результата или до перехода в состояние "ошибка". Соответственно, возвращается или результат, или сообщение о невозможности его получения.

Немного подумав, я решил попробовать вообще отказаться от рекурсии, применив грязный трюк с изменением счетчика цикла "на лету". Вот что получилось в результате.

Code (PHP) : Убрать нумерацию

// Польская нотация. Реализация извратного алгоритма с откатом цикла
// Зато работает быстрее предыдущей функции почти в 2 раза
function polish_distortion($str) {
// подчистить строку и разделить ее на "стек"
$stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
$cnt=count($stack);
for ($i=0; $i<$cnt; $i++) {
if (in_array($stack[$i], array('-', '+', '*', '/'))) {
// debug
//echo join(' ',$stack).'<br>';
if ($i<2) { return 'error'; }
// выполнить операцию, записать в "стек" результат
eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
// изъять из "стека" операнды
unset($stack[($i-1)]);
unset($stack[($i-2)]);
$stack=array_values($stack);
// откат цикла
$i=0;
$cnt=count($stack);
}
}
return $stack[0];
}

Ну и напоследок небольшой код для тестирования обеих функций. В нем по 1000 раз вызывается каждая из функций с одинаковым исходным примером и замеряется время выполнения каждого варианта. Результаты получаются очень любопытные.

Code (PHP) : Убрать нумерацию

// Вспомогательная функция получения точного времени
function gettime() {
$part_time = explode(' ',microtime());
$real_time = $part_time[1].substr($part_time[0],1);
return $real_time;
}
// Расчет примера по функции с рекурсией
$start_time = gettime();
for ($i=0; $i<1000; $i++) {
$tmp=polish_recursive('8 3 5 * + 3 4 + * 5 - 8 +');
}
$stop_time = gettime();
$diff_time = bcsub($stop_time,$start_time,6);
echo 'Variant 1: '.$diff_time;
echo '<br>';
// Расчет примера по функции с откатом цикла
$start_time = gettime();
for ($i=0; $i<1000; $i++) {
$tmp=polish_distortion('8 3 5 * + 3 4 + * 5 - 8 +');
}
$stop_time = gettime();
$diff_time = bcsub($stop_time,$start_time,6);
echo 'Variant 2: '.$diff_time;

Результаты тестов у меня получились следующие: функция с откатом цикла работает почти в два раза быстрее "политкорректной" функции с рекурсией. Так что в очередной раз убедились, что выбор решения целиком и полностью зависит от постановки начальной задачи, и не надо бояться принимать нестандартные решения.

Просмотров: 8306 | Комментариев: 7

Метки: PHP

Внимание! Статья опубликована больше года назад, информация могла устареть!

не буду спорить с правописанием Polskiej stronie но алгоритм и правописание
тут свободное или или все зависит как переменные выставишь х=0 или труе или фалше возможны варианты как константу в датабас обозначаешь

ManHunter (20.01.2011 в 10:43):

Ну с простым вычислением в строчку конечно не сравнится, разница даже не в разы, а на порядки больше.

А польская нотация применяется в классическом варианте языка Форт, когда-то давно я на нем пытался программировать. Еще в лицейские годы мне довелось поработать на старых советских калькуляторах, в которых расчеты проводились по такому же принципу: сперва вводились числа, а потом выбирались действия над ними. Приходилось сперва на бумажке разворачивать обычный арифметический пример в польский вариант записи, а потом производить расчеты. Так что алгоритм не такой уж и редкий.

Вадим (20.01.2011 в 00:50):

Спасибо, интересно, не знал о существовании такого алгоритма.

А если сравнить с результатом обычного расчёта?

Добавить комментарий

Заполните форму для добавления комментария

Если программист в девять утра уже на работе, значит он там же и ночевал

Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина

Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал

Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.

Метки статей

Свернуть

Вам помог этот сайт?

Поблагодарили 35,663 раза

День информатики

День заказов подарков и написания писем Деду Морозу

Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите

Ctrl

Enter

Буду очень благодарен, если размеcтите мою кнопочку:

<a href="https://www.manhunter.ru" target="_blank"><img src="https://www.manhunter.ru/images/button.gif" alt="Личный блог ManHunter'а" title="Личный блог ManHunter'а" width="88" height="31" /></a>

$Яндекс тИЦ: {YANDEX_TIC}$

Яндекс ИКС: 360

Сейчас я слушаю

---

- автообновление

Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 2 (0.0071 сек.) / Память: 4.5 Mb

	2024 - ДЕКАБРЬ
Пн	Вт	Ср	Чт	Пт	Сб	Вс
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Решение примера в обратной польской нотации

Комментарии

Добавить комментарий