Sunday, 31 May 2015

Evaluate Postfix


Algorithm to follow :
    Scan the characters in the expression , and
    for each character
        If the character is an operand , push it to stack
        If the character is an operator , pop the operands , evaluate result and push result back to stack
    After the loops ends scanning and evaluating , pop the value from stack and return it as the final value of the postfix expression
   

int evaluatePostfix(char* exp)
{
    //create a stack equal to expression size
    struct Stack* stack = createStack(strlen(exp));
   
    //check if stack was created successfully
    if (!stack) return -1;

    //scan all characaters in the expression one by one
    for (int i = 0; exp[i]; ++i)
    {
        //if the scanned character is a number ,push it on the stack
        if (isdigit(exp[i]) ) push(stack , ( exp[i] - '0' ) );

        //else pop the operands from stack and push back the result after evaluation
        else
        {
            int value1 = pop(stack);
            int value2 = pop(stack);
            switch (exp[i])
            {
            case '+':
                push(stack , value2 + value1 ); // value2 is the first operand because it was pushed before value1
                break;
            case '-':
                push(stack, value2 - value1); // value2 is the first operand because it was pushed before value1
                break;
            case '/':
                push(stack, value2 / value1); // value2 is the first operand because it was pushed before value1
                break;
            case '*':
                push(stack, value2 * value1); // value2 is the first operand because it was pushed before value1
                break;
            }
        }

    }

    //the last value in the stack is ours final result
    return pop(stack);


}

No comments:

Post a Comment