1 // This solution performs all operations on strings with the mixed radix.
    2 //
    3 // Author: Matt Eastman
    4 
    5 #include <iostream>
    6 #include <string>
    7 
    8 #include <assert.h>
    9 #include <stdio.h>
   10 #include <string.h>
   11 #include <unistd.h>
   12 
   13 using std::string;
   14 
   15 class CrazyInt
   16   {
   17   public:
   18     CrazyInt() : valid_(false) { }
   19 
   20     CrazyInt(const string& value) : valid_(true), value_(value)
   21     {
   22       if (!Validate(value))
   23         valid_ = false;
   24     }
   25 
   26     CrazyInt operator-() const
   27       {
   28         if (!valid_) return CrazyInt("");
   29         switch (Sign())
   30           {
   31           case -1:
   32             return CrazyInt(value_.substr(1));
   33           case 0:
   34             return *this;
   35           case 1:
   36             return CrazyInt("-" + value_);
   37           }
   38         assert(false);
   39       }
   40 
   41     CrazyInt operator+(CrazyInt other) const
   42       {
   43         if (!valid_ || !other.valid_) return CrazyInt("");
   44         if (Sign() < 0) return -(-*this + -other);
   45         if (other.Sign() < 0) return *this - -other;
   46         return AddSubInternal(other, true);
   47       }
   48 
   49     CrazyInt operator-(CrazyInt other) const
   50       {
   51         if (!valid_ || !other.valid_) return CrazyInt("");
   52         if (Sign() < 0) return -(-*this - -other);
   53         if (other.Sign() < 0) return *this + -other;
   54         if (other > *this) return -(other - *this);
   55         return AddSubInternal(other, false);
   56       }
   57 
   58     CrazyInt operator--()
   59     {
   60       *this = *this - CrazyInt("1");
   61       return *this;
   62     }
   63 
   64     bool valid() const
   65       {
   66         return valid_;
   67       }
   68 
   69     const string ToString() const
   70       {
   71         if (!valid_) return "Invalid";
   72         return value_;
   73       }
   74 
   75     bool operator>(CrazyInt other) const
   76       {
   77         return Compare(other) > 0;
   78       }
   79 
   80   private:
   81     CrazyInt AddSubInternal(CrazyInt other, bool add) const
   82       {
   83         int buf[buf_size_];
   84         char char_buf[buf_size_];
   85         memset(buf, 0, sizeof(buf));
   86         memset(char_buf, 0, sizeof(char_buf));
   87         int offset = buf_size_ - value_.size();
   88         for (int i = 0; i < value_.size(); i++)
   89           {
   90             buf[offset + i] += Index(value_[i]);
   91           }
   92         offset = buf_size_ - other.value_.size();
   93         for (int i = 0; i < other.value_.size(); i++)
   94           {
   95             if (add)
   96               buf[offset + i] += Index(other.value_[i]);
   97             else
   98               buf[offset + i] -= Index(other.value_[i]);
   99           }
  100 
  101         int last_non_zero = buf_size_ - 1;
  102         int base = 2;
  103         for (int i = buf_size_ - 1; i >= 0; i--)
  104           {
  105             if (buf[i] >= base)
  106               {
  107                 buf[i - 1] += buf[i] / base;
  108                 buf[i] %= base;
  109               }
  110             while (buf[i] < 0)
  111               {
  112                 buf[i] += base;
  113                 buf[i - 1]--;
  114               }
  115             char_buf[i] = charset_[buf[i]];
  116             if (buf[i] != 0)
  117               last_non_zero = i;
  118             base++;
  119           }
  120 
  121         return CrazyInt(string(char_buf, buf_size_).substr(last_non_zero));
  122       }
  123 
  124     int Sign() const
  125       {
  126         assert(valid_);
  127         assert(!value_.empty());
  128         if (value_[0] == '-')
  129           return -1;
  130         if (value_ == "0")
  131           return 0;
  132         return 1;
  133       }
  134 
  135     int Compare(CrazyInt other) const
  136       {
  137         assert(valid_ && other.valid_);
  138         if (Sign() < other.Sign()) return -1;
  139         if (Sign() > other.Sign()) return 1;
  140         if (Sign() < 0) return -((-*this).Compare(-other));
  141         if (value_.size() < other.value_.size()) return -1;
  142         if (value_.size() > other.value_.size()) return 1;
  143         if (value_ < other.value_) return -1;
  144         if (value_ > other.value_) return 1;
  145         return 0;
  146       }
  147 
  148     static int Index(char c)
  149     {
  150       for (int i = 0; charset_[i] != '\0'; i++)
  151         {
  152           if (charset_[i] == c)
  153             return i;
  154         }
  155       return -1;
  156     }
  157 
  158     static bool Validate(const string& value)
  159     {
  160       if (!value.empty() && value[0] == '-')
  161         {
  162           return Validate(value.substr(1));
  163         }
  164       if (value.empty() || value.size() >= 36)
  165         {
  166           return false;
  167         }
  168       int base = value.size() + 1;
  169       for (int i = 0; i < value.size(); i++)
  170         {
  171           int digit = Index(value[i]);
  172           if (digit < 0 || digit >= base)
  173             {
  174               return false;
  175             }
  176           base--;
  177         }
  178       return true;
  179     }
  180 
  181     static const char* charset_;
  182     static const int buf_size_ = 40;
  183     bool valid_;
  184     string value_;
  185   };
  186 
  187 const char* CrazyInt::charset_ = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  188 
  189 int main(int argc, char** argv)
  190 {
  191 #ifdef DEBUG
  192   FILE* fp = fopen("input", "r");
  193   assert(fp != NULL);
  194   dup2(fileno(fp), fileno(stdin));
  195 #endif
  196 
  197   int num_lines;
  198   assert(scanf("%d", &num_lines) == 1);
  199   for (int i = 0; i < num_lines; i++)
  200     {
  201       char str_a[1024];
  202       char str_b[1024];
  203       char op;
  204       assert(scanf(" %s %c %s", str_a, &op, str_b) == 3);
  205       CrazyInt a(str_a);
  206       CrazyInt b(str_b);
  207       CrazyInt result;
  208       if (op == '+') result = a + b;
  209       else if (op == '-') result = a - b;
  210       std::cout << result.ToString() << std::endl;
  211     }
  212   return 0;
  213 }
  214