java - 使用递归评估后缀表达式

Question

我需要一种使用递归评估后缀表达式的算法。在这个后缀表达式中，操作数可以多于一位。空格用于区分两个操作数。所以表达式 '45 68 +' 是有效的。

我想过反向评估它，但我认为这不应该是正确的。

有人可以帮我解决算法。

提前致谢。

Answer 1

不会让我觉得这是一个递归友好的问题。但我确信可以这样做。

我想到了两种方法：

选项#1：使函数递归调用和返回匹配维基上描述的堆栈推送和弹出操作。

这种方法的缺点是您会很快发现从函数返回的数据可能相当复杂。它可能是一个操作员。也许有一个可选的操作数（IE：数字）。您将返回可能应该对它们进行操作（方法）的结构/对象。

选项#2：每个递归调用处理输入流的下一个字符。

我认为这种方法将作为参数传入堆栈，并且可能是当前数字的“累加器”——在将数字推入堆栈之前将数字累加到一个数字中。将返回一个大量的尾递归数字结果。

这种方法实际上只是将循环重写为递归。

无论哪种方式，自己弄清楚应该是具有挑战性和教育意义的！

Answer 2

以下是一种伪代码，适用于带有 +/- 的后缀表达式。我认为你可以进一步扩展这个想法。如果您仍然遇到困难，请给我发邮件到 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;

}