teaching machines

CS 330 Lecture 14 – Stack API

February 22, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• why malloc?
• a stack API
• evaluating postfix expressions
• for each token
• if token is number, push it on operand stack
• if token is operator, pop two operands, push result back on
• pop stack to get the value
• separate compilation
• command-line arguments
• atoi

TODO

• Read http://www.joelonsoftware.com/articles/fog0000000319.html.
• Read http://gee.cs.oswego.edu/dl/html/malloc.html.

Code

makefile

EXES = first arrays months oob strings test_stack

all: $(EXES)

$(EXES): %: %.c
	gcc -o $@ -Wall -std=c99 $< stack.c

clean:
	rm -f $(EXES)

stack.h

#ifndef STACK_H
#define STACK_H

struct stack_t {
  int *elements;
  int top;
};

struct stack_t *make_stack(int nelements);

// Add element to stack
void push(struct stack_t *stack, int new_thing);

int pop(struct stack_t *stack);

int peek(const struct stack_t *stack);

#endif

stack.c

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

#include "stack.h"

/* ------------------------------------------------------------------------- */

struct stack_t *make_stack(int nelements) {
  struct stack_t *new_stack = (struct stack_t *) malloc(sizeof(struct stack_t));
  new_stack->elements = (int *) malloc(sizeof(int) * nelements);
  new_stack->top = 0;
  return new_stack;
}

/* ------------------------------------------------------------------------- */

int peek(const struct stack_t *stack) {
  assert(stack->top > 0);
  return stack->elements[stack->top - 1];
}

/* ------------------------------------------------------------------------- */

int pop(struct stack_t *stack) {
  assert(stack->top > 0);
  --stack->top;
  return stack->elements[stack->top];
}

/* ------------------------------------------------------------------------- */

void push(struct stack_t *stack, int new_thing) {
  stack->elements[stack->top] = new_thing;
  stack->top++;
}

test_stack.c

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "stack.h"

int main(int argc, char **argv) {
  struct stack_t *operands = make_stack(100);

  for (int i = 0; i < argc; ++i) {
    if (isdigit(argv[i][0])) {
      push(operands, atoi(argv[i]));
    } else if (strcmp(argv[i], "*") == 0) {
      int b = pop(operands);
      int a = pop(operands);
      push(operands, a * b);
    } else if (strcmp(argv[i], "+") == 0) {
      int b = pop(operands);
      int a = pop(operands);
      push(operands, a + b);
    }
  }

  printf("%d\n", pop(operands));
  
  /* push(operands, 10); */
  /* push(operands, 13); */
  /* push(operands, 17); */

  /* for (int i = 0; i < 3; ++i) { */
    /* printf("pop(operands): %d\n", pop(operands)); */
  /* } */

  return 0;
}

Haiku