Convertir préfixe à postfix, à l'aide de la pile

M'a dit d'écrire un programme en tournant le préfixe forme de postfix formulaire à l'aide de la pile.

La sortie j'ai maintenant doit être correcte lorsque j'utilise du papier et un crayon pour mettre en œuvre la fonction. Cependant, le résultat s'affichera dans la fenêtre de commande est étrange.

De sortie réelle:

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

Correcte de sortie:

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+-/

Code:

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();
    }

}
}
InformationsquelleAutor Ruka Tsoi | 2013-10-29
  1. 1

    Il semble que vous êtes familier avec les bases de la POO alors je vous suggère de prendre un nettoyant approche.
    Pour moi, il semble préférable de générer un Arbre de préfixe, puis obtenir le postfix par un gauche-rencontre-droit de la Profondeur de la première itération.

    La partie la plus difficile est la génération d'un arbre , d'abord envisager d'avoir une structure appelée 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;
    }
};

    Voici l'arbre du générateur:

    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;
}

    et enfin la fonction qui génère Postfix de l'arbre.

    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;
}
    InformationsquelleAutor Sachamora