计算中缀表达式而不将其转换为后缀[duplicate]

Question

我试图在1次传递中评估一个内插表达式，而不将其转换为后缀，但它没有为某些表达式提供正确的输出。例如：3-5*10/5 10 , (45 5)-5*(100/10) 5

是否有人能在cpp中为这个问题提供适当的解决方案。

链接到上一个问题：如何使用堆栈在一次扫描中计算中缀表达式？

请不要将其标记为重复，因为我已经尝试了上述给定线程中回答的算法，但没有效果。

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

Answer 1

您的代码只能处理一位数的操作数，并且它没有检查格式错误的输入，因此当您有一个多位数的操作数时，它会运行异常。

对于前者，最简单的修复方法就是在看到数字时扫描数字——将if（isoperand（exp[i]）子句更改为：

    if (isdigit(exp[i])) {
        int value = 0;
        while (isdigit(exp[i]))
            value = value * 10 + exp[i++] - '0';
        s1.push(value);
    } else ...

对于错误检查，您应该执行以下操作

• 检查空格和其他无效字符，并拒绝或跳过它们
• 跟踪最后匹配的标记是操作数还是运算符，并为两个连续的操作数或除（和）以外的两个连续运算符提供错误