-1

スタックを使用して前置形式を後置形式に変換するプログラムを作成するように言われました。
紙と鉛筆を使用して関数を実装すると、今の出力は正しいはずです。ただし、コマンド ウィンドウに表示される結果は奇妙です。

実際の出力:

prefix  : A
postfix : A

prefix  : +*AB/CD
postfix : AB*CD/+

prefix  : +-*$ABCD//EF+GH
postfix : AB$C*D-EF/GH+/H

prefix  : +D/E+$*ABCF
postfix : DEAB*C$F+/F

prefix  : /-*A+BCD-E+FG
postfix : ABC+DEFG+-+FG

正しい出力:

prefix  : A
postfix : A

prefix  : +*AB/CD
postfix : AB*CD/+

prefix  : +-*$ABCD//EF+GH
postfix : AB$C*D-EF/GH+/+

prefix  : +D/E+$*ABCF
postfix : DEAB*C$F+/+

prefix  : /-*A+BCD-E+FG
postfix : ABC+*D-EFG+-/

コード：

void prefix_to_postfix(string& prefix, string& postfix)
{
//Convert the input prefix expression to postfix format

postfix = prefix;   //initialize the postfix string to the same length of the         prefix string

stack<stackItem> S;
stackItem x;
int k = 0;  //index for accessing char of the postfix string

for (int i = 0; i < prefix.length(); i++)  //process each char in the prefix string from left to right
{
    char c = prefix[i];

    if(prefix.length() == 1)
        break;

    //Implement the body of the for-loop        
    if(isOperator(c))
    {
        x.symb = c;
        x.count = 0;
        S.push(x);
    }
    else
    {
        S.top().count++;
        postfix[k++] = c;

        if(S.top().count == 2)
        {
            postfix[k++] = S.top().symb;
            S.pop();
            S.top().count++;
        }
    }
    if(i == (prefix.length() - 1))
    {
        postfix[k++] = S.top().symb;
        S.pop();
    }

}
}
4

1 に答える 1

1

あなたは OOP の基本に精通しているようですので、よりクリーンなアプローチを取ることをお勧めします。私には、最初にプレフィックスからツリーを生成し、次に左と右の深さの最初の反復によってポストフィックスを取得する方が良いようです。

難しい部分はツリーを生成することです。まず、TNode と呼ばれる構造を持つことを検討してください。

class TNode
{
private:
    TNode* _left;
    TNode* _right;
public:
    TNode* Parent;
    char Symbol;
    bool IsOperand;
    TNode(char symbol , bool isOperand)
    {
        Symbol = symbol;
        IsOperand = isOperand;
        Parent = NULL;
        _left = NULL;
        _right = NULL;
    }     
    void SetRight(TNode* node)
    {
        _right = node;
        node->Parent = this;
    }

    void SetLeft(TNode* node)
    {
        _left = node;
        node->Parent = this;
    }

    TNode* GetLeft()
    {
        return _left;
    }

    TNode* GetRight()
    {
        return _right;
    }
};

ツリージェネレーターは次のとおりです。

TNode* PostfixToTree(string prefix)
{
    TNode* root = NULL;
    TNode* nodeIter = NULL;
    char c;
    for(int i=0 ; i<prefix.length() ; i++)
    {
        c = prefix[i];
        if(root == NULL)
        {
            if(!isOperand(c))
            {
                root = new TNode(c,false);
                nodeIter = root;
            }
            else return NULL;
        }
        else
        {
            while(true)
            {
                if(nodeIter->GetLeft() == NULL && !isOperand(nodeIter->Symbol))
                {
                    nodeIter->SetLeft(new TNode(c,isOperand(c)));
                    nodeIter = nodeIter->GetLeft();
                    break;
                }
                else if(nodeIter->GetRight() == NULL && !isOperand(nodeIter->Symbol))
                {
                    nodeIter->SetRight(new TNode(c,isOperand(c)));
                    nodeIter = nodeIter->GetRight();
                    break;
                }
                else
                {
                    while(isOperand(nodeIter->Symbol) ||
                        nodeIter->GetRight()!=NULL && nodeIter->GetLeft()!=NULL &&
                        nodeIter->Parent!=NULL)
                    {
                        nodeIter = nodeIter->Parent;
                    }
                }
            }

        }

    }

    return root;
}

最後に、ツリーから Postfix を生成する関数です。

string TreeToPostfix(TNode* root)
{
    string postfix = "";
    stack<TNode*> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty())
    {
        TNode* top = nodeStack.top();
        nodeStack.pop();
        postfix = top->Symbol + postfix;
        if(top->GetLeft()!=NULL)
            nodeStack.push(top->GetLeft());
        if(top->GetRight()!=NULL)
            nodeStack.push(top->GetRight());
    }
    return postfix;
}
于 2014-05-26T14:36:48.793 に答える