C Lab 2 – Implementing a Stack

Due Sunday 11 April 11:59pm

Introduction

In previous classes you covered the basics of pointers, allocating memory from the heap, and writing code for linked lists. In this class we covered how these basics work in C. For example malloc(sizeof(int)) allocates memory from the heap and free(memorypointer)  deallocates memory. This assignment is geared at applying your pointer/memory skills to C.

Task

The program template you should use is template.c Your task is to  implement a simple stack based reverse Polish notation calculator using a linked list. For example, if I type the 4 lines:

PUSH 5

PUSH 4

ADD

POP

Your program should output

9

The commands you need to implement are as follows:

PUSH

Push a number onto the stack, printing nothing. For example, PUSH 5, pushes the number 5 onto the stack.

POP

Pops a number off the stack and prints it followed by a newline. If the stack is empty POP will print the string NULL.

PEEK

Prints the top number on the stack. If the stack is empty it will print the string NULL. It does not alter the stack

PRINTSTACK

Prints the entire stack starting from the top. Each number is on a separate line followed by a newline. If the stack is empty PRINTSTACK will print nothing. For example

PUSH 19

PUSH 50

PUSH 21

PRINTSTACK

will print

21

50

19

Again, calling PRINTSTACK on an empty stack will print nothing.

CLEAR

Removes all numbers from the stack

ADD

pops 2 numbers from the stack, adds them, and puts the result on the stack. If there are not two numbers on the stack nothing is pushed on the stack and nothing is printed.

SUBTRACT

Pops one number from the stack (n1); pops another (n2); subtracts n1 from n2 and puts the result on the stack. If there are not two numbers on the stack nothing is pushed on the stack and nothing is printed.

Examples

Should output

29
48

The following

POP
PUSH 19
PUSH 50
PUSH 21
PRINTSTACK
SUBTRACT
PEEK
ADD
POP
POP

Should output

NULL
21
50
19
29
48
NULL

How to submit

Submit your code to Submit-O-Matic.

Grading

6 points if your code produces correct results on Submit-O-Matic. And code review shows understanding of linked lists.

2 points if your code produces correct results locally.

0 points otherwise.