中缀到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转换

回答

相关问题