Kyrieh Girls 2007-2008

Source Code

• Source Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <cstdlib>
using namespace std;

const int mx = 100;
const int LIM = 8;
const int Zeit = 100;

char s0[mx], ss[mx];
int f[mx], lst[mx], tp, len, tlen, tab[Zeit][30], zt;
unsigned long long tv[Zeit];

void init();
void random();
unsigned long long calc(int, int);

int main()
{
  srand(time(NULL));

  for(int i = 0; i < Zeit; i++) 
    for(int j = 0; j < 30; j++) tab[i][j] = rand() % LIM;

  while(gets(s0) && strcmp(s0, ".")) {
    init();
    for(zt = 0; zt < Zeit; zt++) tv[zt] = calc(0, len);
    while(gets(s0) && strcmp(s0, ".")) {
      init();
      for(zt = 0; zt < Zeit; zt++) if(calc(0, len) != tv[zt]) break;
      printf("%s\n", (zt == Zeit) ? "yes" : "no");
    }
    printf(".\n");
  }
  return 0;
}

int get_digit(int pos, int dir)
{
  for(int i = pos; ; i += dir) {
    if(i < 0 || i >= tlen) return 0;
    if(isdigit(s0[i])) return 1;
    if(s0[i] != ' ') return 0;
  }
}

void init()
{
  tlen = strlen(s0);
  len = 0;

  for(int i = 0; i < tlen; i++) 
    if(s0[i] != ' ') ss[len++] = s0[i];
    else if(get_digit(i, -1) && get_digit(i, 1)) ss[len++] = s0[i];

  ss[len] = 0;
  
  tp = 0;
  for(int i = 0; i < len; i++) 
    if(ss[i] == '(') lst[tp++] = i;
    else if(ss[i] == ')') f[lst[--tp]] = i;
}

unsigned long long read(int& pos)
{
  int vr(-1), pwr(1);
  unsigned long long ret;
  
  if(isdigit(ss[pos])) {
    for(ret = 0; pos < len && isdigit(ss[pos]); pos++) ret = ret * 10 + ss[pos] - '0';
    pos--;
    return ret;
  }
  
  ret = 1;
  vr = ss[pos] - 'a';

  if(ss[++pos] == '^') pwr = ss[++pos] - '0'; 
  else --pos;
  
  for(int i = 0; i < pwr; i++) ret *= tab[zt][vr];
  return ret;
}

unsigned long long calc(int l, int r)
{
  int sig(1), flag(0);
  unsigned long long ret(0), buf(0), tmp;

  for(int i = l; i <= r; i++) 
    if(i == r || ss[i] == '+' || ss[i] == '-') {
      ret += sig * buf; 
      flag = 0;
      if(i < r && ss[i] == '-') sig = -1;
      else sig = 1;
    }
    else if(ss[i] == '(') {
      tmp = calc(i + 1, f[i]);
      if(flag) buf = buf * tmp; else buf = tmp;
      flag = 1;
      i = f[i];
    }
    else if(ss[i] != ' ') {
      tmp = read(i);
      if(flag) buf = buf * tmp; else buf = tmp;
      flag = 1;
    }

  return ret;
}