Week 10 Laboratory — Sample Solutions

  1. bracketsQ.c

    // bracketsQ.c: check whether stdin contains balanced (), [] and {}
    #include <stdio.h>
    #include <stdlib.h>
    #include "quack.h"
    #define OPENA '('
    #define CLOSA ')'
    #define OPENB '{'
    #define CLOSB '}'
    #define OPENC '['
    #define CLOSC ']'
    
    int main() {
      Quack st;
      char bracket;
      st = createQuack();
      int mismatch = 0;
    
      while ((bracket = getchar()) != EOF && !mismatch) {
         if (bracket == OPENA || bracket == OPENB || bracket == OPENC) {
            push((int)bracket, st); // cast the char to an int before pushing
         } else if (bracket == CLOSA || bracket == CLOSB || bracket == CLOSC) {
            if (isEmptyQuack(st)) {
               mismatch = 1;         // an opening bracket is missing
            } else {
               char closing = (char)pop(st); // cast the int to char after popping
               if (!((closing == OPENA && bracket == CLOSA) ||
                     (closing == OPENB && bracket == CLOSB) ||
                     (closing == OPENC && bracket == CLOSC))) {
                   mismatch = 1;    // opening and closing brackets are different
               }
            }
         }
      }
      if (!isEmptyQuack(st) || mismatch) {
         printf("unbalanced\n");
      } else {
         printf("balanced\n");
      }
      return EXIT_SUCCESS;
    }
    

  2. recountplus.c

    // recountplus.c: recursively count from 0 to argv[1],
    // where argv[1] is a non-negative integer
    #include <stdlib.h>
    #include <stdio.h>
    
    void printn(int, int); // a recursive function
    
    int main(int argc, char *argv[]) {
       int endcount = 0;
       int retval;
       if ((argc != 2) || (sscanf(argv[1], "%d", &endcount) != 1)) {
          fprintf(stderr, "Usage: %s number\n", argv[0]);
          retval = EXIT_FAILURE;
       } else {
          printn(0, endcount); // print from 0 to endcount recursively
          retval = EXIT_SUCCESS;
       }
       return retval;
    }
    
    void printn(int number, int limit) {
       if (number == limit) {     // base case
          printf("%d\n", number);
       } else if (number < limit) { // inductive case
          printf("%d,", number);
          printn(++number, limit);
       }
       // if (number > limit) do nothing
    }
    

  3. recount.c

    // recount.c: count from 0 to argv[1], where argv[1] is +ive or -ive
    #include <stdlib.h>
    #include <stdio.h>
    
    void printn(int, int); // a recursive function
    
    int main(int argc, char *argv[]) {
       int endcount = 0;
       int retval;
       if ((argc != 2) || (sscanf(argv[1], "%d", &endcount) != 1)) {
          fprintf(stderr, "Usage: %s number\n", argv[0]);
          retval = EXIT_FAILURE;
       } else {
          printn(0, endcount); // print from 0 to endcount recursively
          retval = EXIT_SUCCESS;
       }
       return retval;
    }
    
    void printn(int number, int limit) {
       printf("%d", number);
       if (number == limit) {     // base case
          printf("\n");
       } else if (number < limit) { // +ive inductive case
          printf(",");
          printn(++number, limit);
       } else {                     // -ive inductive case
          printf(",");
          printn(--number, limit);
       }
    }
    

  4. sumTree.c

    // sumTree.c: input and pretty-print a BST and sum its nodes
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
       int value;
       struct node *left;
       struct node *right;
    } Node;
    typedef Node *Tree;
    
    Node *newNode(int v);              // make a new node, from lecture
    Tree insert(Tree t, int v);        // insert a node 'v' into a BST, from lecture
    
    void printTree(Tree t, int level); // print a BST, starting at level=0,1,2...
    int  sumTree(Tree t);              // sum all the nodes in the tree t
    void freeTree(Tree t);             // free the tree
    
    int main(int argc, char *argv[]) {
       Tree t = NULL;
       int i;
       int dataGood = 1;
       int retval = EXIT_SUCCESS;
    
       if (argc == 1) {
          fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
          retval = EXIT_FAILURE;
       } else {
          for (i=1; i<argc && dataGood; i++) {
             int num;
             if (sscanf(argv[i], "%d", &num) != 1) {
                fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
                freeTree(t);
                dataGood = 0;
             } else {
                t = insert(t, num);
             }
          }
          if (dataGood) {
             printTree(t, 0);
             printf("Sum of nodes = %d\n", sumTree(t));
             freeTree(t);
          } else {
             retval = EXIT_FAILURE;
          }
       }
       return retval;
    }
    
    void printTree(Tree t, int depth) {
       if (t != NULL) {
          depth++;
          printTree(t->left, depth);
          int i;
          for (i=1; i<depth; i++) {
              putchar('\t');
          }
          printf("%d\n", t->value);
          printTree(t->right, depth);
       }
    }
    
    int sumTree(Tree t) { // sum all the nodes in the tree t
       int sum = 0;
       if (t != NULL) {
          sum = t->value + sumTree(t->left) + sumTree(t->right);
       }
       return sum;
    }
    
    void freeTree(Tree t) { // free in postfix fashion
       if (t != NULL) {
          freeTree(t->left);
          freeTree(t->right);
          free(t);
       }
    }