Оценка выражения postfix с использованием рекурсии - PullRequest
Новая
       24

Оценка выражения postfix с использованием рекурсии

1 голос
/ 10 ноября 2011

Мне нужен алгоритм для оценки выражения postfix с использованием рекурсии.В этом постфиксном выражении операнд может содержать более одной цифры.Пробел используется для различения двух операндов.Таким образом, выражение «45 68 +» является действительным.

Я думал о том, чтобы оценить его в обратном направлении, но я думаю, что это не должно быть правильным.

Может кто-нибудь помочь мне только с алгоритмом.

Заранее спасибо.

Ответы [ 2 ]

1 голос
/ 10 ноября 2011

Ниже приведен псевдокод, который будет работать с постфиксными выражениями с +/-.Я думаю, что вы можете расширить эту идею.Если вы все еще испытываете трудности, напишите мне на 2shanks.p@gmail.com, так как я не регулярно бываю на этом сайте. 

void recursivePostfix(char* expr)  
{  
if(!expr)   return;  

bool flag=true;
static double result=0;
double v1=result, v2=0, dec=0;
char oper='0';
int i=0, state=1;

do
{
    if('0' != oper)
    {
        switch(oper)
        {
            case '+': result=v1+v2; break;
            case '-': result=v1-v2; break;
            case '*': result=v1*v2; break;
            case '/': result=v1/v2; break;
        }
        oper = '0';
        v1 = result;
        v2 = 0;
        recursivePostfix(expr+i);
    }

    if(SPACE_CHAR == *(expr+i) && state++)
        continue;

    switch(state)
    {
        case 1:
            v1 = v1*10 + (expr[i]-'0'); break;
        case 2:
            v2 = v2*10 + (expr[i]-'0'); break;
        case 3:
            oper = *(expr+i);
    }  
}while(0 != *(expr+i++));
cout << result;

}
1 голос
/ 10 ноября 2011

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

Мне приходят на ум два подхода:

Опция # 1: Сделать функциональные вызовы рекурсии и возвраты совпадающими со стековыми операциями push и popописано в вики.

Недостатком этого подхода является то, что вы быстро обнаружите, что возвращаемые данные из функции могут быть довольно сложными.Вероятно, это будет оператор.Может быть, с необязательным операндом (IE: номер).Вы будете возвращать структуры / объекты, которые, возможно, должны иметь операции (методы) над ними.

Опция # 2: Каждый рекурсивный вызов обрабатывает следующий символ входного потока.

Я думаю, что этот подход передал бы в качестве параметров стек и, возможно, «накопитель» для текущего числа - для накопления цифр в числе перед помещением его в стек.Будет возвращен один массивный числовой результат с хвостовой рекурсией.

Этот подход на самом деле просто переписывает цикл как рекурсию.

В любом случае, выяснить это самостоятельно должно быть сложно и познавательно!

...