2

再帰を使用して後置式を評価するためのアルゴリズムが必要です。この後置式では、オペランドに複数の数字を指定できます。2 つのオペランドを区別するためにスペースが使用されます。したがって、「45 68 +」という表現は有効です。

逆に評価しようと思ったのですが、それは正しくないと思います。

誰かがアルゴリズムだけで私を助けてくれますか?

前もって感謝します。

4

2 に答える 2

2

再帰に優しい問題だとは思いません。しかし、私はそれがそのように行うことができると確信しています。

私には2つのアプローチが思い浮かびます。

オプション #1: 関数の再帰呼び出しとリターンを、Wiki で説明されているスタックのプッシュおよびポップ操作と一致させます。

このアプローチの欠点は、関数から返されるデータがかなり複雑になる可能性があることにすぐに気付くことです。おそらくオペレーターでしょう。オプションのオペランド (IE: 数値) を使用することもできます。おそらく操作（メソッド）が必要な構造/オブジェクトを返します。

オプション #2: 各再帰呼び出しは、入力ストリームの次の文字を処理します。

このアプローチは、パラメーターとしてスタックと、おそらく現在の数値の「アキュムレータ」を渡すと思います-スタックにプッシュする前に数字を数値に累積します。大規模な末尾再帰の数値結果が 1 つ返されます。

このアプローチは、実際にはループを再帰として書き換えているだけです。

いずれにせよ、自分でそれを理解することは挑戦的で教育的でなければなりません!

于 2011-11-10T03:23:50.850 に答える
1

以下は、 +/- を使用した後置式で機能する一種の疑似コードです。アイデアをさらに広げることができると思います。それでも問題が解決しない場合は、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;

}
于 2011-11-10T10:25:18.313 に答える