Evaluate Infix expression without converting it into postfix

Question

I'm trying to evaluate an infix expression in 1 pass without converting it into postfix but it's not giving correct output for some expressions. For eg: 3-5*10/5+10 , (45+5)-5*(100/10)+5

Can someone provide a proper solution to this problem in cpp.

Link to the previous question asked: How to evaluate an infix expression in just one scan using stacks?

Please don't mark it as duplicate as I have tried the algorithm answered in the above given thread but to no avail.

#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

Your code can only deal with single-digit operands -- and it has no checks for malformed input, so when you have a multi-digit operand, it runs off the rails.

The easiest fix for the former is just to scan digits when you see a digit -- change the if (isoperand(exp[i]) clause to:

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

For error checking, you should do things like

• check for spaces and other invalid characters and reject or skip them
• keep track of whether the last token matched was an operand or an operator, and give errors for two consecutive operands, or two consecutive operators other than ( and )