FriedSpace.com

Space for Cooking up Great Ideas

Space for Cooking up Great Ideas

FriedSpace

Module 2

Other Modules

Announcements

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.