Write the file prefix.c with the the following functions. Include prefix.h as the header In this part you will write a calculator for arithmetic expressions in prefix notation. 9) Write a function that gets an array of tokens representing an arithmetic expression in the prefix notation, and computes the evaluation of the expression. Use the stack evaluation discussed in class. int prefix_eval_tokens( char ** prefix_expr, int n_tokens) Examples: On input [ "+", "5", "-", "7", "2" ] the function will return 10. This is because the expression is : ( 5 + ( 7 - 2 ) ) = 10 . * You may assume that all intermediate values in the computation are between 0 and 99 ** You may assume that the results of all division operations are integers. *** You may use the stack implementation given in the assignment. The data in stack is of type void * . Use casting if necessary. 10) Use the functions in part 1 and prefix_eval to write a function that gets a string representing an arithmetic expression in prefix notation and evaluates the corresponding expression. int prefix_eval( char * expression) * You may assume that all intermediate values in the computation are between 0 and 99 ** You may assume that the results of all division operations are integers. *** You may assume that all expression are formatted correctly. Examples: "/ 25 5" "+ 5 - 7 2" "- / + 15 13 - 5 1 + 2 4"

prefix.c

#include #include #include

#include "prefix.h"

int prefix_eval_token(char** prefix_expr, int n_tokens) { // implement me return 0; }

int prefix_eval(char* prefix_expr) { // implement me return 0; }

prefix.h

#ifndef PREFIX_H #define PREFIX_H

// gets an array of tokens representing an arithmetic expression in the prefix notation // returns the evaluation of the expression int prefix_eval_token(char** prefix_expr, int n_tokens);

// gets a string representing an arithmetic expression in prefix notation // and evaluates the corresponding expression. int prefix_eval(char* prefix_expr);

#endif

stack.h

#ifndef STACK_H #define STACK_H

struct node { void* data; struct node* next; }; typedef struct node node_t;

typedef struct { node_t* top; } stack_t;

// creates a new stack stack_t* stack_create();

// pushes a given item to the stack // Pre condition: stack is not empty void stack_push(stack_t* s, void* item);

// pops the top element from the stack // Pre condition: stack is not empty void* stack_pop(stack_t* s);

// returns 1 if the stack is empty, and returns 0 otherwise int stack_is_empty(stack_t* s);

// releases the memory used by the stack void stack_free(stack_t* s);

#endif

stack.c

#include #include

#include "stack.h"

// creates a new stack stack_t* stack_create() { stack_t* s = (stack_t*) malloc(sizeof(stack_t)); s->top = NULL; return s; }

// pushes a given item to the stack // Pre condition: stack is not empty void stack_push(stack_t* s, void* item) { node_t* newTop = (node_t*) malloc(sizeof(node_t)); newTop->data = item; newTop->next = s->top; s->top = newTop; }

// pops the top element from the stack // Pre condition: stack is not empty void* stack_pop(stack_t* s) { void* ret = s->top->data; node_t* prevTop = s->top; s->top = prevTop->next; free(prevTop); return ret; }

// returns 1 if the stack is empty, and returns 0 otherwise int stack_is_empty(stack_t* s) { return (s->top == NULL); }

void stack_free(stack_t* s) { while (s->top) { node_t* prevTop = s->top; s->top = prevTop->next; free(prevTop); } free(s); }