Решение примера в обратной польской нотации
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];
- }
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;
Просмотров: 8168 | Комментариев: 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
--- - ---- = ---- - -------
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?
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 или труе или фалше возможны варианты как константу в датабас обозначаешь
тут свободное или или все зависит как переменные выставишь х=0 или труе или фалше возможны варианты как константу в датабас обозначаешь
ManHunter
(20.01.2011 в 10:43):
Ну с простым вычислением в строчку конечно не сравнится, разница даже не в разы, а на порядки больше.
А польская нотация применяется в классическом варианте языка Форт, когда-то давно я на нем пытался программировать. Еще в лицейские годы мне довелось поработать на старых советских калькуляторах, в которых расчеты проводились по такому же принципу: сперва вводились числа, а потом выбирались действия над ними. Приходилось сперва на бумажке разворачивать обычный арифметический пример в польский вариант записи, а потом производить расчеты. Так что алгоритм не такой уж и редкий.
А польская нотация применяется в классическом варианте языка Форт, когда-то давно я на нем пытался программировать. Еще в лицейские годы мне довелось поработать на старых советских калькуляторах, в которых расчеты проводились по такому же принципу: сперва вводились числа, а потом выбирались действия над ними. Приходилось сперва на бумажке разворачивать обычный арифметический пример в польский вариант записи, а потом производить расчеты. Так что алгоритм не такой уж и редкий.
Вадим
(20.01.2011 в 00:50):
Спасибо, интересно, не знал о существовании такого алгоритма.
А если сравнить с результатом обычного расчёта?
А если сравнить с результатом обычного расчёта?
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 34,326 раз
Поблагодарили 34,326 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 380 |
 |
 |