# Random

astack.c

#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "STACK.h"

static Item *s;
static int N;

void STACKinit(int maxN) {
  s = malloc(maxN*sizeof (Item));
  N = 0;
}

int STACKempty() {
  return N == 0;
}

void STACKpush(Item item) {
  // ここに式を書く
  s[N] = item;
  N++;
}

Item STACKpop() {
  // ここに式を書く
  N--;
  return s[N];
}

void STACKprint() {
  for (int i=N-1; i>=0; i--) {
    printItem(s[i]);
    printf(" ");
  }
  printf("\n");
}

postfix.c

/*
  後置記法の算術式を計算して結果を返す
  入力: ./postfix '5 9 8 + 4 6 * * 7 + *'
  出力: 2075
 */


#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"

int main(int argc, char *argv[]) {
  char *a = argv[1]; // 引数の算術式を格納する配列
  int N = strlen(a); // 配列の大きさ

  // stackの初期化
  STACKinit(N);

  //  文字列の先頭から最後まで繰り返す
  for (int i=0; i<N; i++) {
    // 文字が'+'だったら、stackの1番上と2番目の値をstackからpopして、加算してstackにpush
    if (a[i] == '+'){
      // ここに式を書く
      int n1 = STACKpop();
      int n2 = STACKpop();
      STACKpush(n1+n2);
    }

    // 文字が'*'だったら、stackの1番上と2番目の値をstackからpopして、乗算してstackにpush
    if (a[i] == '*'){
      // ここに式を書く
      int n1 = STACKpop();
      int n2 = STACKpop();
      STACKpush(n1*n2);
    }

    // 以下は、文字が'0'-'9'の数字の場合の処理
    if ((a[i] >= '0') && (a[i] <= '9')){
      // とりあえず0をstackにpushする
      STACKpush(0);
    // stackの１番めを10倍したものとa[i]の値を加算しstackにpush。iをインクリメント
      while ((a[i] >= '0') && (a[i] <= '9')){
      // ここに式を書く
        int n = STACKpop();
        STACKpush(10*n+a[i]-'0');
        i++;
      }
    }
  }

  // 最終的にstackの値をpopして出力
  printf("%d \n", STACKpop());
}

in2post.c

/*
  入力: in2post '(5*((9+8)*(4*6))+7))'
  出力: 5 9 8 + 4 6 * * 7 + *
 */


#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"

int main(int argc, char *argv[]) {
  char *a = argv[1];
  int N = strlen(a);

  STACKinit(N);

  // ここに処理を書く
  for(int i = 0; i<N; i++){
    /*STACKprint();*/
    if(a[i] == ')'){
      printf("%c ",STACKpop());
    }
    else if ((a[i] >= '0') && (a[i] <= '9')){
      int n = 0;
      while ((a[i] >= '0') && (a[i] <= '9')){
        n *= 10, n += (a[i]-'0');
        i++;
      }
      printf("%d ", n);
      i--;
    }
    else if(a[i] == '*' || a[i] == '+'){
      STACKpush(a[i]);
    }
  }
}

main.c

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

/*
                E
              /   \
	     /     \
            D       H
           / \     / \
          B       F
         / \     / \
        A   C       G
       / \ / \     / \

*/


int count(link h) {
  if (h == NULL)
    return 0;
  return count(h->l) + count(h->r) + 1/* ここに式 */ ;
}

int height(link h) {
  int u, v;

  if (h == NULL)
    return -1;
  u = height(h->l)/* ここに式 */;
  v = height(h->r)/* ここに式 */;
  if (u > v)
    return u + 1;
  else
    return v + 1;
}

void printnode(char c, int h) {
  int i;
  for (i = 0; i < h; i++) 
    printf("  ");
  printf("%c\n", c);
}

void show(link x, int h) {
  if (x == NULL) {
    printnode('*', h);
    return;
  }
  show(x->r, h+1);
  printnode(x->item, h);
  show(x->l, h+1);
}

int main(void) {
  link root, left, right;

  root = new_node('E', NULL, NULL);
  add_left_leaf(root, 'D');
  add_right_leaf(root, 'H');
  left = root->l;
  add_left_leaf(left, 'B');
  left = left->l;
  add_left_leaf(left, 'A');
  add_right_leaf(left, 'C');
  right = root->r;
  add_left_leaf(right, 'F');
  right = right->l;
  add_right_leaf(right, 'G');

  show(root, 1);

  printf("Number of nodes: %d\n", count(root));
  printf("Height of the tree: %d\n", height(root));

  return 0;
}

exptotree.c

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

Item* add(link* p, Item* c){
    if (*c == '\0')return '\0';
    while (1) {
        Item* q;
        if(*p == NULL)*p = new_node(*c, NULL, NULL);
        else {
            if(*c >= 'a' && *c <= 'z')return c;
            q = add(&(*p)->l, c + 1);
            q = add(&(*p)->r, q + 1);
            return q;
        }
    }
}

void infix(link p){
    if(p == NULL)return;
    if(p->item < 'a' || p->item >'z')printf("(");
    infix(p->l);
    printf("%c", p->item);
    infix(p->r);
    if(p->item < 'a' || p->item >'z')printf(")");
}

void postfix(link p){
    if(p == NULL)return;
    postfix(p->l);
    postfix(p->r);
    printf("%c", p->item);
}

int main(void) {
    const int MX = 500;
    char exp[MX];
    scanf("%s", exp);
    link root = NULL;
    add(&root, exp);
    infix(root);
    printf("\n");
    postfix(root);
    return 0;
}

heap.c

#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "heap.h"

void fixUp(Item a[], int k) {
  while (k > 0) {
    // 課題：以下のAとして正しいkの式を入れなさい．ex. k-1
    if (less(a[k], a[k-1])) { // 自分と親の値を比べて必要なら交換する
      exch(a[k], a[k-1]);
    }
    k = k-1; // 親ノードに移動する
  }
}

void fixDown(Item a[], int k, int N) {
  int j;
  // 課題：以下のBとして正しいkの式を入れなさい．ex. k-1
  while (k+1 <= N) { // インデックスkの左の子を調べる
    j = k;
    if (a[j] > a[j+1]) // 左の子が小さければ左に移動
      j++;
    if (j > N)
      break;
    if (a[j] >= a[k])
      break;
    exch(a[k], a[j]); // 子ノードの値と交換
    k = j;
  }
}

void PQinit(int maxN) {
  pq = malloc((maxN+1)*sizeof(Item));
  N = 0;
}

int PQempty(void) {
  return N == 0;
}

void PQinsert(Item v) {
  pq[N] = v;
  N = N+1;
  fixUp(pq, N-1);
}

Item PQdelmin() {
  Item v = pq[0];
  pq[0] = pq[N-1];
  N = N-1;
  fixDown(pq, 0, N-1);
  return v;
}

st.c

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

typedef struct STnode* link;
struct STnode {
  Item item;
  link next;
};
static link *heads, z;
static int N, M;

int hash(char *v, int M) {
  int h;
  int a = 127;

  for (h = 0; *v != '\0'; v++)
    h = (a*h + *v) % M;
  return h;
}

int eq(char *a, char *b) {
  return (strcmp(a, b) == 0);
}

static link NEW(Item item, link next) {

    link x = malloc(sizeof *x);

    x->item = item;
    x->next = next;
  return x;
}

Item searchR(link t, Key v) {
    if (t == z)
        return NULLitem;
    if (eq(key(t->item), v))
        return t->item;
    return searchR(t->next, v);
}

Item search(link h, Key v) {
  while (h != z) {
    if (eq(key(h->item), v))
    	return h->item;
    h = h->next;
  }
  return z->item;
}

void STinit(int max) {
  int i;
  
  N = 0;
  M = max/5;
  heads = malloc(M*sizeof(link));
  z = NEW(NULLitem, NULL);
  for (i = 0; i < M; i++)
    heads[i] = z;
}

void STinsert(Item item) {
    int i = hash(key(item), M);
    heads[i] = NEW(item, heads[i]);
    N++;
}

Item STsearch(Key v) {
    return searchR(heads[hash(v, M)], v);
}

link delete(link h, Item item) {
    link l = h, t;
    if (l == z)
        return z;
    if (eq(key(l->item), key(item))) {
        h = l->next;
        free(l);
        return h;
    }
    t = l->next;
    while (t != z) {
        if (eq(key(t->item), key(item))) {
      // add expression here
            h = t->next;
           free(t);
           break;
    }
    l = l->next;
    t = t->next;
  }
  return h;
}

void STdelete(Item item) {
  int i = hash(key(item), M);

  heads[i] = delete(heads[i], item);
}

st2.c

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

#define null(A) (key(st[A]) == key(NULLitem))

static int N, M;
static Item *st;

int hash(char *v, int M) {
  int h;
  int a = 127;

  for (h = 0; *v != '\0'; v++)
    h = (a*h + *v) % M;
  return h;
}

int eq(char *a, char *b) {
  return (strcmp(a, b) == 0);
}

void STinit(int max) {
  int i;

  N = 0;
  M = 2*max;
  st = malloc(M*sizeof(Item));
  for (i = 0; i < M; i++)
    st[i] = NULLitem;
}

int STcount(void) {
  return N;
}

void STinsert(Item item) {
  Key v = key(item);
  int i = hash(v, M);

  while(!null(i))
    i = (i+1) % M;
  st[i] = item;
  N++;
}

Item STsearch(Key v) {
  int i = hash(v, M);
  while (!null(i))
    if (eq(v, key(st[i])))
      return st[i];
    else
      i = (i+1) % M;
  return NULLitem;
}

void STdelete(Item item) {
  int j, i = hash(key(item), M);
  Item v;

  while(!null(i))
    if (eq(key(item), key(st[i])))
      break;
    else
        // add expression here
        i = (i+1) % M;
  if (null(i))
    return;
  st[i] = NULLitem;
  N--;
  for (j = i+1; !null(j); j = (j+1) % M, N--) {
    v = st[j];
    st[j] = NULLitem;
    // add expression here
    st[j-1] = v;
  }
}