Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Web-мастеру и не только | Автор: ManHunter
Обратная польская нотация - один из классических алгоритмов, используемых в вычислительной технике. Он используется для вычислений, и особенностью является следование символов операций за символами операндов, а также в отсутствии скобок. Если интересно, можете почитать описание алгоритма польской нотации. Листая сайт с вакансиями, я наткнулся на одно предложение работы, где в качестве тестового задания требовалось написать функцию, которая получает строку примера, записанного в обратной польской нотации, и возвращает результат вычислений. Сама вакансия для меня никакого интереса не представляла, с работой у меня все в порядке, а задание показалось интересным. Вот что у меня сперва получилось.
  1. // Польская нотация. Реализация алгоритма с рекурсией
  2. function polish_recursive($str) {
  3.     // подчистить строку и разделить ее на "стек"
  4.     $stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
  5.  
  6.     $cnt=count($stack);
  7.     // если в стеке более 1 элемента
  8.     if ($cnt>1) {
  9.         // debug
  10.         //echo join(' ',$stack).'<br>';
  11.  
  12.         // пройтись по стеку
  13.         for ($i=0$i<$cnt$i++) {
  14.             // знак арифметического действия?
  15.             if (in_array($stack[$i], array('-''+''*''/'))) {
  16.                 // слева осталось меньше двух цифр?
  17.                 if ($i<2) { return 'error'; }
  18.                 // выполнить операцию, записать в "стек" результат
  19.                 eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
  20.                 // изъять из "стека" операнды
  21.                 unset($stack[($i-1)]);
  22.                 unset($stack[($i-2)]);
  23.                 break;
  24.             }
  25.             else {
  26.                 // не арифметический знак и не число
  27.                 if (!is_numeric($stack[$i])) { return 'error'; }
  28.             }
  29.         }
  30.         // в стеке ничего не изменилось после выполнения цикла
  31.         if ($cnt==count($stack)) { return 'error'; }
  32.  
  33.         // следующий рекурсивный проход
  34.         $str=polish_recursive(join(' ',$stack));
  35.     }
  36.     // результат
  37.     return($str);
  38. }
В решении реализован псевдо-стек в массиве, а вычисление выполняется рекурсивно до получения результата или до перехода в состояние "ошибка". Соответственно, возвращается или результат, или сообщение о невозможности его получения.

Немного подумав, я решил попробовать вообще отказаться от рекурсии, применив грязный трюк с изменением счетчика цикла "на лету". Вот что получилось в результате.
  1. // Польская нотация. Реализация извратного алгоритма с откатом цикла
  2. // Зато работает быстрее предыдущей функции почти в 2 раза
  3. function polish_distortion($str) {
  4.     // подчистить строку и разделить ее на "стек"
  5.     $stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
  6.  
  7.     $cnt=count($stack);
  8.     for ($i=0$i<$cnt$i++) {
  9.         if (in_array($stack[$i], array('-''+''*''/'))) {
  10.             // debug
  11.             //echo join(' ',$stack).'<br>';
  12.  
  13.             if ($i<2) { return 'error'; }
  14.  
  15.             // выполнить операцию, записать в "стек" результат
  16.             eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
  17.             // изъять из "стека" операнды
  18.             unset($stack[($i-1)]);
  19.             unset($stack[($i-2)]);
  20.             $stack=array_values($stack);
  21.  
  22.             // откат цикла
  23.             $i=0;
  24.             $cnt=count($stack);
  25.         }
  26.     }
  27.     return $stack[0];
  28. }
Ну и напоследок небольшой код для тестирования обеих функций. В нем по 1000 раз вызывается каждая из функций с одинаковым исходным примером и замеряется время выполнения каждого варианта. Результаты получаются очень любопытные.
  1. // Вспомогательная функция получения точного времени
  2. function gettime() {
  3.     $part_time explode(' ',microtime());
  4.     $real_time $part_time[1].substr($part_time[0],1);
  5.     return $real_time;
  6. }
  7.  
  8. // Расчет примера по функции с рекурсией
  9. $start_time gettime();
  10. for ($i=0$i<1000$i++) {
  11.     $tmp=polish_recursive('8  3 5 * + 3   4 +  * 5  - 8 +');
  12. }
  13. $stop_time gettime();
  14. $diff_time bcsub($stop_time,$start_time,6);
  15. echo 'Variant 1: '.$diff_time;
  16.  
  17. echo '<br>';
  18.  
  19. // Расчет примера по функции с откатом цикла
  20. $start_time gettime();
  21. for ($i=0$i<1000$i++) {
  22.     $tmp=polish_distortion('8  3 5 * + 3   4 +  * 5  - 8 +');
  23. }
  24. $stop_time gettime();
  25. $diff_time bcsub($stop_time,$start_time,6);
  26. echo 'Variant 2: '.$diff_time;
Результаты тестов у меня получились следующие: функция с откатом цикла работает почти в два раза быстрее "политкорректной" функции с рекурсией. Так что в очередной раз убедились, что выбор решения целиком и полностью зависит от постановки начальной задачи, и не надо бояться принимать нестандартные решения.

Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 5996 | Комментариев: 7

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

Комментарии

Отзывы посетителей сайта о статье
ManHunter (21.04.2011 в 10:30):
Что это было?
Михаил (21.04.2011 в 09:19):
a+b       a-b        b       b*b-ab
              ---     - ----    = ----  -  -------
              2(a-b)    2(a+b)    a+b      a*a-b*b
ManHunter (26.01.2011 в 18:07):
object0, very interesting. I'll think about it.
object0 (26.01.2011 в 16:13):
It's me again ;)

Google Calculator formats math expressions this way:
2+2/2 ---> 2 + (2 / 2)
2+2/2*PI ---> 2 + ((2 / 2) * PI)

Well, it adds brackets. I need a JS/PHP function which returns a formatted math expression the same way. Can you help me out with this?
bigcatwar (21.01.2011 в 18:14):
не буду спорить с правописанием Polskiej stronie но алгоритм и правописание
тут свободное или или все зависит как переменные выставишь х=0 или труе или фалше возможны варианты как константу в датабас обозначаешь
ManHunter (20.01.2011 в 10:43):
Ну с простым вычислением в строчку конечно не сравнится, разница даже не в разы, а на порядки больше.

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

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

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.06 сек. / MySQL: 2 (0.0034 сек.) / Память: 4.5 Mb
Наверх