The Stack

Now we recall that the correct procedure when a number is encountered in the polish postfix expression is to push something onto a stack. In fact we won't push the current number on the stack, but store this where we have just put it, i.e. in currentNum. But this means that the previous value of currentNum (if there is one) ought to be pushed onto the stack first. We will write a new function whose purpose will be to push a number onto the stack.

In order to implement our stack, we will use the linked list structure which we described earlier. The stack will just be a linked list of items going from the top of the stack down to the bottom. Firstly we add the following type definition at the top of our file (but after the preprocessor directives):

typedef struct node
    int numdata;
    struct node * nextnode;
} node;

Within our calculate function we add the pointer to the top of our stack (which we set to NULL for now):

node * stackTop = NULL;

One slight difficulty with not pushing numbers onto the stack immediately is that we have no idea whether the integer currentNum has already been assigned or not. There are various ways to deal with this, however we will simply define a flag (actually just a variable of type int) which will be 0 if currentNum has not previously been assigned a value, and 1 otherwise. Thus we add the following line to our calculate function.

int assigned = 0;

We will call our stack pushing function pushItem and it will take two arguments. The first will be a pointer, which will point to the top item of the stack. The second will be the integer that we wish to push. It will look as follows-na:

node * pushItem(node * stackTop, int number)
    static node * newItem;
    newItem = calloc(sizeof(node),1);
    newItem->numdata = number;
    newItem->nextnode = stackTop;
    return newItem;

This ought to be pretty self explanatory apart from the word static in front of the definition of newItem. This tells C that it ought to retain newItem and anything that it points to when the function returns. The default without this word is to clean up any local variables and things they may point to, destroying the data which we have just gone to the trouble to save.

Now that we have our stack pushing function, we are in a position to finish the part of our calculate function which processes a number. We add the following lines before the variable currentNum is set to the new value:

if (assigned)
    stackTop = pushItem(stackTop, currentNum);
} else assigned = 1;

Note that since there is only a single statement to follow the else clause, we can omit the curly braces which are normally included.

It should be clear what is going on here. The stack pushing function creates a new node, puts the integer in it and sets this new node to point to the old top of the stack. A pointer to this new node is then returned and made the new stack top.

Now that we have completely dealt with any incoming numbers, we turn to the other part of our calculate function, which deals with any arithmetic operators.