Обратная польская нотация - один из классических алгоритмов, используемых в вычислительной технике. Он используется для вычислений, и особенностью является следование символов операций за символами операндов, а также в отсутствии скобок. Если интересно, можете почитать описание алгоритма польской нотации. Листая сайт с вакансиями, я наткнулся на одно предложение работы, где в качестве тестового задания требовалось написать функцию, которая получает строку примера, записанного в обратной польской нотации, и возвращает результат вычислений. Сама вакансия для меня никакого интереса не представляла, с работой у меня все в порядке, а задание показалось интересным. Вот что у меня сперва получилось.
// Польская нотация. Реализация алгоритма с рекурсией
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);
}
В решении реализован псевдо-стек в массиве, а вычисление выполняется рекурсивно до получения результата или до перехода в состояние "ошибка". Соответственно, возвращается или результат, или сообщение о невозможности его получения.
Немного подумав, я решил попробовать вообще отказаться от рекурсии, применив грязный трюк с изменением счетчика цикла "на лету". Вот что получилось в результате.
// Польская нотация. Реализация извратного алгоритма с откатом цикла
// Зато работает быстрее предыдущей функции почти в 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 раз вызывается каждая из функций с одинаковым исходным примером и замеряется время выполнения каждого варианта. Результаты получаются очень любопытные.
// Вспомогательная функция получения точного времени
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;
Результаты тестов у меня получились следующие: функция с откатом цикла работает почти в два раза быстрее "политкорректной" функции с рекурсией. Так что в очередной раз убедились, что выбор решения целиком и полностью зависит от постановки начальной задачи, и не надо бояться принимать нестандартные решения.