使用堆棧將前綴轉換爲後綴

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

看來你很熟悉面向對象基礎，所以我建議採取一個更簡潔的方法。 對我來說，首先從前綴中生成一個Tree似乎更好，然後通過左右深度第一次迭代得到後綴。

困難的部分是產生一棵樹，首先考慮具有稱爲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; 
} 

，最後從所述生成後綴的功能樹。

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