Search code examples
c++expressionexpression-evaluation

Why isn't work when trying subtraction in postfix evaluation?


I'm trying to getting result from postfix. But it gives me wrong when subtraction, and don't know why. Please give many helps for c++ newbie.

I got two operands from stack. And tried subtraction "last popped" - "first popped".

/*pf_exp is postfix expression. String type*/
for (int i=0; i<pf_exp.length(); i++)
{
    int sub_result; // saving result.
    if (48 <= (int)pf_exp[i] && (int)pf_exp[i] <= 57)
    {
        operands.push((int)pf_exp[i] - 48);
    }
    else
    {
        /*operators is a stack<int> from '#include<stack>' storing operands.*/
        int operand2 = operands.top();
        operands.pop();
        int operand1 = operands.top();
        operands.pop();
        if(pf_exp[i] == '+')
        {
            sub_result = operand1 + operand2;
        }
        else if(pf_exp[i] == '-')
        {
            sub_result = operand1 - operand2;
        }
        else if(pf_exp[i] == '*')
        {
            sub_result = operand1 * operand2;
        }
        else if(pf_exp[i] == '/')
        {
            sub_result = operand1 / operand2;
        }
        operands.push(sub_result);
    }
}

I expect the output of "789--" to be "-10" but the actual output is "8".


Solution

  • You are probably thinking of the stack as a queue. You expect (7 - 8) - 9 = -10, but, since you are using a stack, the items added last are returned, so as Ben wrote, you are actually doing 7 - (8 - 9) = 8. Use a queue instead, and change the order of the operands to get what you actually wanted.

    UPDATE

    Sorry, my explanation did not take the postfix evaluation into account. As the comment states, it should always use a stack by definition. Nonetheless, my answer probably explains, why you were thinking of the wrong result.