0

C++ で中置式を評価 (変換ではなく) したいと考えています。アルゴリズムまたはそのようなアルゴリズムの実装さえも所有している場合 (C++ でなくても、任意の言語である可能性があります... C++ に書き直そうとします) 共有してください。

評価手段は式の値を与える。(2+2)*3 は 12

申し訳ありませんが、スタック ソリューションについて話していることを忘れていました。ツリー ソリューションを知っているため、今回は適切ではありません : (。

4

2 に答える 2

3

どうやって表現を得たのですか？あなたがそれを好きなら(3 + 4) - (1 * 2) + 1 =

                  +  
            /          \
           -            1
     /          \   
    +            *          
 /     \      /    \
3      4    1       2

http://cboard.cprogramming.com/cplusplus-programming/32682-inserting-infix-into-binary-tree.html

Left Root Right3 + 4 結果 - 1 の結果 * 2 結果 + 1 .

スタックのようにアセンブリをシミュレートできるような式34+12*-1+を取得した場合、演算子に到達した場合は、スタック内の最後の 2 つの要素をポップし、演算子を適用します。3 をスタックに入れ、4 をスタックに入れ、op を取得します。+ 最後の 2 つの要素をポップして、演算子を使用します。これで、スタックに 7 つしかありません。演算子を取得するまで読み取ります。スタックには、op の後に 7 1 2 があります。* スタックでは、op の後に 7 2 を取得しました。- スタックに 5 しかないスタックに 1 を追加: スタック 5 1、最後の演算子 + を使用して、最終結果 6 を取得します。

わかりました、ここにコードがあります：

#include <STACK>

int GetResult( char * rpn ) 
{
    std::stack<int> myStack;

    int nr1, nr2; int length = strlen(rpn);

    for (int i = 0; i < length; i++)
    {
        if (isdigit(rpn[i]))
        {
            myStack.push(rpn[i] - '0');
        }
        else
        {
            switch(rpn[i])
            {
                case '+':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 + nr1);
                    break;

                case '-':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 - nr1);
                    break;

                case '*':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 * nr1);
                    break;

                case '/':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 / nr1);
                    break;
                default:
                    break;
            }
        }
    }

    return myStack.top();
}

int main(int argc, char* argv[])
{
    char *rpn = "34+12*-1+";

    int rez = GetResult(rpn);

    printf("%i", rez);

    return 0;
}
于 2012-08-25T13:08:49.190 に答える
1

最も簡単な方法は、 Dijkstra の Shunting-yard アルゴリズムを使用して中置式を後置記法に変換し、その結果を評価することです。これは簡単なことです。このコード サンプルはインターネット上にあります ( Rosetta コードまたはLiterateProgramsを参照してください)。

または、学習したい場合、および構文解析とコンパイラ理論の魔法の世界に入りたい場合は、再帰降下パーサーを作成します。それはとても楽しいです。

ああ、さらに堅牢なものが必要な場合は、Pratt 解析を参照してください。これはすばらしいものです。これについての素晴らしい記事があります。

于 2012-08-25T13:11:23.083 に答える