<分区>
我试图在 1 遍中评估中缀表达式而不将其转换为后缀,但它没有为某些表达式提供正确的输出。例如:3-5*10/5+10 , (45+5)-5*(100/10)+5
有人可以在 cpp 中为这个问题提供适当的解决方案吗?
上一个问题的链接:How to evaluate an infix expression in just one scan using stacks?
请不要将其标记为重复,因为我已经尝试了上述给定线程中回答的算法但无济于事。
#include<bits/stdc++.h>
int isoperand(char x)
{
if(x == '+' || x=='-'|| x=='*' || x=='/' || x==')' || x=='(')
return 0;
return 1;
}
int Pre(char x)
{
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 3;
return 0;
}
int infixevaluation(std::string exp)
{
std::stack<int> s1; //Operand Stack
std::stack<char> s2; //Operator Stack
int i,x,y,z,key;
i=0;
while(exp[i]!='\0')
{
if(isoperand(exp[i]))
{
key = exp[i]-'0';
s1.push(key);
i++;
}
else if(!isoperand(exp[i]) && s2.empty())
s2.push(exp[i++]);
else if(!isoperand(exp[i]) && !s2.empty())
{
if(Pre(exp[i])>Pre(s2.top()) && exp[i]!=')')
s2.push(exp[i++]);
else if(exp[i]==')' && s2.top() == '(')
{
s2.pop();
i++;
}
else if(exp[i]=='(')
s2.push(exp[i++]);
else
{
x = s1.top();
s1.pop();
y = s2.top();
s2.pop();
z = s1.top();
s1.pop();
if(y == '+')
s1.push(z+x);
else if(y == '-')
s1.push(z-x);
else if(y == '*')
s1.push(x*z);
else if(y == '/')
s1.push(z/x);
}
}
}
while(!s2.empty())
{
x = s1.top();
s1.pop();
y = s2.top();
s2.pop();
z = s1.top();
s1.pop();
if(y == '+')
s1.push(x+z);
else if(y == '-')
s1.push(z-x);
else if(y == '*')
s1.push(x*z);
else if(y == '/')
s1.push(z/x);
}
return s1.top();
}
int main(int argc, char const *argv[])
{
std::string s;
getline(std::cin,s);
std::cout<<infixevaluation(s)<<std::endl;
return 0;
}