Note: All code should be written within this template directory. Test cases have been provided in the folder tests, and can be run using make test.

Stacks: A first data structure

The stack is one of the most basic data structures you will ever use. In fact, your computer keeps track of how functions call each other using a stack (called the 'call stack').

In its barest form, it can be implemented as a singly-linked list which allows you to add and remove elements only to/from the front (also known as the 'head') of the list.

Implement a stack with at least the following operations:

• Stack* stack_new(): Creates a new, empty stack.
• void stack_delete( Stack* st ): Deletes the stack, freeing all memory.
• Stack* stack_push( Stack* st, int val ): Inserts val to the top of the stack. Should return st (Note: By returning the same input, you can chain together many functions like stack_pop( stack_pop( st ) ), etc. ).
• int stack_top( Stack* st, int* error ): Returns the element currently at the top of the stack. If the stack is empty, error should be set to 1, else 0. (Note: error is an argument passed by reference - give it the address to a locally defined integer.)
• Stack* stack_pop( Stack* st ): Deletes the value at the top of the stack. Remember to free memory.
• int stack_size( Stack* st ): Return the number of elements in the stack.
• void stack_print( Stack* st ): Iterates over the entire stack, printing its elements one by one - separated by spaces.

Evaluating Postfix Expressions

In this exercise, we will evaluate postfix expressions like "3 4 +" (which evaluates to 7). Postfix notation is particularly easy to program for, because all it requires is a stack.

Define a function int evaluate_postfix( char* expr ) that takes a postfix expression as input, and evaluates it. Use strtok to process the string. Support addition (+), subtraction (-), multiplication (*), and division (/). When dividing, use integer division.

Write a program using your stack library, and evaluate function that takes in only a postfix expression as input (use fgets ), and prints the evaluated value.

Sample Input/Output

Input: 3 4 + 7 * 3 - 5 /
Output: Print the output of the stack after each operation
9