» CS 330 Lecture 14

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

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

show