스택을 사용하여 접두사를 접미사로 변환합니다.

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

상기에서 접미사를 생성 함수 마침내 : 여기

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라는 구조를 고려해 나무.

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