Thursday lecture code

////////////////////////////////////////////////////////////////////////
// COMP2521 19x1 ... a generic item type
//
// 2018-09-28    Jashank Jeremy <jashankj@cse.unsw.edu.au>

#include <stdbool.h>
#include <stdlib.h>

#ifndef CS2521__ITEM_H_
#define CS2521__ITEM_H_

#define __unused __attribute__((unused))

typedef int Item;

static inline Item item_clone (Item it) { return it; }
static inline void item_drop (Item it __attribute__((unused))) { return; }
static inline bool item_eq (Item a, Item b) { return a == b; }
static inline int item_ord (Item it __unused) { return 1; }
static inline char *item_show (Item it) {
	char *x; asprintf (&x, "%d", it); return x; }
static inline size_t item_size (Item it __unused) { return sizeof(Item); }

#define Item Item

#endif // !defined(CS2521__ITEM_H_)

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- Stacks!
//
// 2018-11-22	Jashank Jeremy <jashankj@cse.unsw.edu.au>

#include <stdlib.h>
#include "item.h"

#ifndef CS2521__STACK_H_
#define CS2521__STACK_H_

typedef struct stack *Stack;

/** Create a new, empty Stack. */
Stack stack_new (void);

/** Destroy a Stack, releasing all resources associated with it. */
void stack_drop (Stack);

/** Remove an item from the top of a Stack. */
Item stack_pop (Stack s);

/** Add an item to the top of a Stack. */
void stack_push (Stack, Item);

/** Get the number of items in a Stack. */
size_t stack_size (Stack);

#endif // !defined(CS2521__STACK_H_)

#include <assert.h>
#include <err.h>
#include <stdlib.h>
#include <sysexits.h>

#include "stack.h"

#define MAX_SIZE 10

typedef struct stack stack;

struct stack {
	Item items[MAX_SIZE];
	size_t n_items;
};

/** Create a new, empty Stack. */
stack *stack_new (void)
{
	stack *new = malloc (sizeof *new);
	if (new == NULL) err (EX_OSERR, "couldn't allocate stack");
	(*new) = (stack) { .items = {}, .n_items = 0 };
	return new;
}

/** Destroy a Stack. */
void stack_drop (stack *s)
{
	free (s);
}

/** Remove an item from the top of a Stack. */
Item stack_pop (stack *s)
{
	assert (s != NULL);
	assert (s->n_items > 0);
	Item it = s->items[s->n_items - 1];
	s->n_items--;
	return it;
}

/** Add an item to the top of a Stack. */
void stack_push (stack *s, Item it)
{
	assert (s != NULL);
	assert (s->n_items < MAX_SIZE - 1);
	s->items[s->n_items] = it;
	s->n_items++;
	return;
}

/** Get the number of items in a Stack. */
size_t stack_size (stack *s)
{
	assert (s != NULL);
	return s->n_items;
}

#include <assert.h>
#include <err.h>
#include <stdlib.h>
#include <sysexits.h>

#include "stack.h"

typedef struct stack stack;
typedef struct stack_item stack_item;

struct stack {
	struct stack_item {
		Item item;
		struct stack_item *next;
	} *top;
	size_t n_items;
};

/** Create a new, empty Stack. */
stack *stack_new (void)
{
	stack *new = calloc (1, sizeof (stack));
	if (new == NULL) err (EX_OSERR, "couldn't allocate stack");
	return new;
}

/** Destroy a Stack, releasing all resources associated with it. */
void stack_drop (stack *s)
{
	assert (s != NULL);

	stack_item *tmp, *curr = s->top;
	while (curr != NULL) {
		tmp = curr->next;
		free (curr);
		curr = tmp;
	}

	free (s);
}

/** Remove an item from the top of a Stack. */
Item stack_pop (stack *s)
{
	assert (s != NULL);
	assert (s->top != NULL);
	stack_item *top = s->top;
	Item it = top->item;
	s->top = top->next;
	free (top);
	s->n_items--;
	return it;
}

/** Add an item to the top of a Stack. */
void stack_push (stack *s, Item it)
{
	assert (s != NULL);
	stack_item *new = malloc (sizeof (stack_item));
	if (new == NULL) err (EX_OSERR, "couldn't allocate stack_item");
	(*new) = (stack_item){ .item = it, .next = s->top };
	s->top = new;
	s->n_items++;
}

/** Get the number of items in a Stack. */
size_t stack_size (stack *s)
{
	return s->n_items;
}

#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>

#include "stack.h"

static void underflow (void) __attribute__((noreturn));

int main (int argc, char *argv[])
{
	if (argc != 2)
		errx (EX_USAGE, "usage: %s 'expression'", argv[0]);

	Stack s = stack_new ();

	char *expr_ = strdup (argv[1]);
	char *expr = expr_;
	char *token;
	while ((token = strsep (&expr, " ")) != NULL) {
		int a, b;
		if (strcmp (token, "+") == 0) {
			if (stack_size (s) < 2) underflow ();
			b = stack_pop (s); a = stack_pop (s);
			stack_push (s, a + b);
		} else if (strcmp (token, "-") == 0) {
			if (stack_size (s) < 2) underflow ();
			b = stack_pop (s); a = stack_pop (s);
			stack_push (s, a - b);
		} else if (strcmp (token, "*") == 0) {
			if (stack_size (s) < 2) underflow ();
			b = stack_pop (s); a = stack_pop (s);
			stack_push (s, a * b);
		} else if (strcmp (token, "/") == 0) {
			if (stack_size (s) < 2) underflow ();
			b = stack_pop (s); a = stack_pop (s);
			stack_push (s, a / b);
		} else {
			stack_push (s, (Item) strtol (token, NULL, 10));
		}
	}

	if (stack_size (s) == 1) {
		printf ("%d\n", stack_pop (s));
	} else {
		printf ("[non-empty stack]\n");
	}

	stack_drop (s);
	free (expr_);
	return EXIT_SUCCESS;
}

static void underflow (void)
{
	errx (EX_SOFTWARE, "underflow!");
}

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

void unmatched (int c);

int main (void)
{
	Stack s = stack_new ();

	int ch;
	while ((ch = getchar ()) != EOF) {
		switch (ch) {
		case '(': case '[': case '{':
			stack_push (s, ch);
			break;
		case ')':
			if (stack_pop (s) != '(') unmatched(ch);
			break;
		case ']':
			if (stack_pop (s) != '[') unmatched(ch);
			break;
		case '}':
			if (stack_pop (s) != '{') unmatched(ch);
			break;
		}

		putchar (ch);
	}

	if (s->n_items != 0)
		unmatched (stack_pop (s));

	stack_drop (s);
	return EXIT_SUCCESS;
}

void unmatched (int c)
{
	printf ("unmatched '%c'\n", c);
	exit (EXIT_FAILURE);
}