使用堆栈将前缀转换为后缀

Question

我被告知编写一个程序，使用堆栈将前缀形式转换为后缀形式。
当我使用纸和铅笔实现该功能时，我现在的输出应该是正确的。 但是，命令窗口中显示的结果很奇怪。

实际输出：

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

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