11724.c

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

typedef struct Node {
  int x;
  int next[26];
  int n;
} Node;

Node nodes[26];
int marked[26];
int val_map[26];

int dfs(int v, int p, int depth) {
  int i;
  int o;
  if (marked[v]) {
    return 1;
  }
  marked[v] = 1;
  val_map[v] = (val_map[v] > depth) ? val_map[v] : depth;
  for (i = 0; i < nodes[v].n; ++i) {
    o = nodes[v].next[i];
    if (dfs(o, v, depth+1)) return 1;
  }
  marked[v] = 0;
  return 0;
}

int main() {
  int n_cases;
  int i,j,k,m,n,ii,jj,kk;
  int ctr;
  char str[1024];
  char ex[1024];
  Node *root;
  int q[1024];
  int st[1024];
  int st_idx;
  int q_idx;
  int len;
  char pred[256];
  int cycle;

  int n_eq;
  memset(pred, 0, sizeof(pred));
  pred['+'] = 1;
  pred['*'] = 2;

  ctr = 0;
  scanf("%d", &n_cases);
  for (ctr = 0; ctr < n_cases; ++ctr) {
    memset(nodes, 0, sizeof(nodes));

    scanf("%s", ex);

    /* parse ex*/
    len = strlen(ex);
    st_idx = 0;
    q_idx = 0;
    for (i = 0; i < len; ++i) {
      if (isalpha(ex[i])) {
        q[q_idx++] = ex[i];
      } else if (pred[ex[i]]) {
        while (st_idx && pred[st_idx-1] >= pred[ex[i]]) {
          q[q_idx++] = st[--st_idx];
        }
        st[st_idx++] = ex[i];
      } else if (ex[i] == '(') {
        st[st_idx++] = '(';
      } else { /*ex[i] == ')'*/
        while (st_idx && st[st_idx-1] != '(') {
          q[q_idx++] = st[--st_idx];
        }
        --st_idx;
      }
    }
    /* pop stuff */
    while (st_idx > 0) {
      q[q_idx++] = st[--st_idx];
    }


    scanf("%d", &n_eq);
    for (i = 0; i < n_eq; ++i) {
      scanf("%s", str);
      char a = str[0] - 'a';
      char b = str[2] - 'a';
      nodes[b].next[nodes[b].n++] = a;
    }

    memset(val_map, 0, sizeof(val_map));

    cycle = 0;
    for (i = 0; i < 26; ++i) {

      memset(marked, 0, sizeof(marked));
      if (dfs(i, -1, 1)) {
        cycle = 1;
        break;
      }

    }

    if (cycle) {
      printf("Case %d: %d\n", ctr+1, -1);
    } else {
      /* evaluate expression */
      st_idx = 0;
      for (i = 0; i < q_idx; ++i) {
        if (isalpha(q[i])) {
          st[st_idx++] = val_map[q[i]-'a'];
        } else if (q[i] == '+') {
          st[st_idx-2] = st[st_idx-1] + st[st_idx-2];
          --st_idx;
        } else { /* q[i] == '*' */
          st[st_idx-2] = st[st_idx-1] * st[st_idx-2];
          --st_idx;
        }
      }

      printf("Case %d: %d\n", ctr+1, st[0]);
    }

  }

  return 0;
}

11724.in

6
a+b+c
3
a>b
b>c
c>b
a+b+c*d
4
a>b
b>c
c>d
d>b
a+b+c
3
a>b
b>c
c>a
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0