/* Problem 7--Off Base
   There was nothing overly difficult about this one; since I do them in
   C, the hairiest part was the parsing. */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define LEN 50

typedef char NT[LEN+2]; /* array big enough to hold number */

int main (int argc, char **argv);
int Parse (FILE *in, NT A, NT B, NT C, char *op);
int SkipBlanks (FILE *in, int f);
int BuildNumber (FILE *in, NT A, char first);
char Convert (char ch);
int MinBase (NT A, NT B, NT C);
int max (int a, int b);
int GetBase (NT A, NT B, NT C, char op);
void Add (NT A, NT B, NT C, int b);
void Subtract (NT A, NT B, NT C, int b);

int main (int argc, char **argv) {

  NT A, B, C;
  char op;
  FILE *in, *out;
  int r, cs, b;

 in = fopen ("prob7.in","r");
 out = fopen ("prob7.out","w");
 cs = 0;
 for (;;) {
 if (Parse (in,A,B,C,&op)) break;
  b = GetBase (A,B,C,op);
  if (b==0) {
   fprintf (out,"Case %d: expression is invalid.\n",++cs);
  } else {
   fprintf (out,"Case %d: minimum base is %d\n",++cs,b);
  }
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* Parse reads in a line of text from in, and computes the three numbers
   A, B, and C and the operator op. It returns true if the line is
   blank, false otherwise. */
int Parse (FILE *in, NT A, NT B, NT C, char *op) {

  int done, ch;

 ch = SkipBlanks (in,' ');
 done = ch=='\n';
 if (!done) {
  ch = BuildNumber (in,A,ch); /* get A */
  ch = SkipBlanks (in,ch);
  *op = ch; /* get op */
  ch = SkipBlanks (in,getc(in));
  ch = BuildNumber (in,B,ch); /* get B */
  ch = SkipBlanks (in,ch);
  ch = SkipBlanks (in,getc(in)); /* skip over = */
  ch = BuildNumber (in,C,ch); /* get c */
  ch = SkipBlanks (in,ch);
 } else {
 }
 return done;
}

/* SkipBlanks reads and discards spaces from in returning the first
   non-space it finds.  f is the lookahead character. */
int SkipBlanks (FILE *in, int f) {

  int ch;

 if (f==' ') {
  for (;;) {
   ch = getc (in);
  if (ch != ' ') break;
  }
 } else {
  ch = f;
 }
 return ch;
}

/* BuildNumber reads a string of alphanumeric characters from in,
   representing the number.  The number is then right-shifted into A.
   first is the lookahead character.  The new lookahead character is
   returned. */
int BuildNumber (FILE *in, NT A, char first) {

  int ch, i, j;

 A[0] = Convert (first);
 i = 1;
 for (;;) { /* read in number */
  ch = getc (in);
 if (!(isdigit (ch) || isalpha (ch))) break;
  A[i] = Convert (ch);
  i++;
 }
 A[LEN+1] = 0;
 j = i-1;
 for (;;) { /* right justify number */
 if (j < 0) break;
  A[j+LEN+1-i] = A[j];
  j--;
 }
 j = LEN-i; /* pad with leading zeroes */
 for (;;) {
 if (j < 0) break;
  A[j] = '0';
  j--;
 }
 return ch;
}

/* Convert shifts down the alphabetic characters so that my digits
   representing 0-35 are a contiguous ASCII sequence. */
char Convert (char ch) {

  char nch;

 if (isalpha (ch)) {
  nch = ch-'A'+'0'+10;
 } else {
  nch = ch;
 }
 return nch;
}

/* MinBase scans A, B, and C and returns what the smallest base could
   possibly be, based on the characters in the arrays. */
int MinBase (NT A, NT B, NT C) {

  int mb, i;

 mb = 2;
 i = 0;
 for (;;) {
 if (i==LEN+1) break;
  mb = max (mb,A[i]-'0'+1);
  mb = max (mb,B[i]-'0'+1);
  mb = max (mb,C[i]-'0'+1);
  i++;
 }
 return mb;
}

/* max returns the maximum of a and b. */
int max (int a, int b) {

  int m;

 if (a > b) {
  m = a;
 } else {
  m = b;
 }
 return m;
}

/* GetBase starts with the smallest possible base and performs the
   arithmetic one base at a time until it finds a match or runs out
   of bases.  It returns true if a matching base was found, false
   otherwise. */
int GetBase (NT A, NT B, NT C, char op) {

  int b, found;
  NT D;

 b = MinBase (A,B,C);
 found = 0;
 for (;;) {
 if (found || b > 36) break;
  if (op=='+') {
   Add (A,B,D,b);
  } else {
   Subtract (A,B,D,b);
  }
  found = strcmp (C,D) == 0;
  b++;
 }
 if (!found) {
  b = 0;
 } else {
  b--;
 }
 return b;
}

/* Sets C equal to A + B in base b. */
void Add (NT A, NT B, NT C, int b) {

  int i, carry, t;

 i = LEN;
 C[i+1] = 0;
 carry = 0;
 for (;;) {
 if (i < 0) break;
  t = A[i]-'0' + B[i]-'0' + carry;
  C[i] = t%b + '0';
  carry = t/b;
  i--;
 }
}

/* Sets C equal to A - B in base b. */
void Subtract (NT A, NT B, NT C, int b) {

  int i, carry, t;

 if (strcmp (A,B) < 0) { /* Is this a valid subtraction? */
  C[0] = 0;
 } else {
  i = LEN;
  C[i+1] = 0;
  carry = 0;
  for (;;) {
  if (i < 0) break;
   t = A[i]-B[i]-carry;
   if (t < 0) {
    C[i] = t+b+'0';
   } else {
    C[i] = t+'0';
   }
   carry = t < 0;
   i--;
  }
 }
}