中綴到Postfix轉換

我正在嘗試將中綴表達式轉換爲後綴表達式的代碼。目前，如果我輸入例如「5 + 6」，程序將正常工作，它將輸出正確的答案，即「5 6 +」。當我輸入多於一個運算符（例如「5 + 6-3」）時，會出現問題，輸出錯誤答案「+ 3-」。有人可以指出我犯的錯誤嗎？提前致謝！中綴到Postfix轉換

void main(){ 

Stack *s = new Stack; 
string input; 


cout <<"Enter Expression"<<endl; 
cin>>input; 

InfixToPostfix(input); 

system("PAUSE"); 

} 





string InfixToPostfix(string input){ 

Stack *S = new Stack(); 

string postfix = ""; 
for (int i=0; i < input.length();i++){ 
    if (input[i]== ' '||input[i]==',') continue; 
    else if (IsOperator(input[i])) 
    { 
     while(!S->IsStackEmpty() && S->StackTop() != '(' && HasHigherPrecedence(S->StackTop(),input[i])) 
     { 
      postfix=S->StackTop(); 
      S->Pop(); 
     } 
     S->Push(input[i]); 
    } 
    else if(IsOperand(input[i])) 
    { 
     postfix +=input[i]; 
    } 
    else if (input[i] == '(') 
    { 
     S->Push(input[i]); 
    } 
    else if (input[i]==')') 
    { 
     while(!S->IsStackEmpty() && S->StackTop() != '('){ 
      postfix += S->StackTop(); 
      S->Pop(); 
     } 
     S->Pop(); 
    } 
} 
while(!S->IsStackEmpty()){ 
    postfix +=S->StackTop(); 

    S->Pop(); 
} 

cout <<""<<postfix; 
return postfix; 

} 

bool IsOperand(char C) 
{ 

if(C>= '0' && C<= '9') return true; 
if(C>= 'a' && C<= 'z') return true; 
if(C>= 'A' && C<= 'Z') return true; 
return false; 
} 

bool IsOperator(char C) 
{ 
if(C=='+' || C== '-' || C =='*' || C == '/' ||C == '$') 

{ 
    return true; 
}else{ 
    return false; 
} 
} 


int IsRightAssociative(char op) 

{ 
if(op=='$'){ 
    return true; 
}else{ 

return false; 
} 
} 
int GetOperatorWeight(char op){ 

int weight = -1; 
switch(op) 
{ 
case'+': 
case '-': 
weight=1; 
break; 
case '*': 
case '/': 
weight=2; 
break; 
case '$': 
weight=3; 
break; 
} 

return weight; 
} 

int HasHigherPrecedence (char op1, char op2) 

{ 

int op1Weight= GetOperatorWeight(op1); 
int op2Weight = GetOperatorWeight(op2); 


if(op1Weight == op2Weight) 
{ 

    if(IsRightAssociative(op1)) 
{ 
     return false; 
    }else{ 
     return true; 
    } 
    return op1Weight > op2Weight ? true:false; 
} 
}

來源

2015-04-07 jkinlol1

這看起來不像C++/CLI。它看起來像普通的C++和一個未知的Stack類... – Medinoc

一個建議：使用樹而不是堆棧作爲中間數據結構。讓優先級最低的運算符成爲樹的根，並從那裏遞歸地構建它。然後再次遞歸地從左到右遍歷樹，以生成後綴版本。這樣，您還可以跟蹤後綴版本的最大堆棧深度，這可能很重要，因爲許多手持式RPN計算器的堆棧深度非常有限。

來源

2015-04-07 00:59:49

感謝您的回覆！是的，我知道使用樹而不是堆棧來實現RPN計算器會更容易。但我已經實現了使用堆棧的後綴，所以我只是打算使用堆棧實現中綴。另外，我對樹木工作的掌握還不是很好，這就是爲什麼我想要使用堆棧。 – jkinlol1

中綴到Postfix轉換

回答

相關問題