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

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)]);