/* roman.cpp - Matt Mahoney, mmahoney@cs.fit.edu

This program is a Roman numeral calculator.  It accepts 3 command
line arguments separated by spaces: a Roman numeral, an arithmetic
operator (+, -, x, or /) and a second Roman numeral.  It outputs
the result of the operation as a Roman numeral and exits.  For
instance:

  roman XVI x V
  LXXX

  roman MM / III
  DCLXVI

Division drops the remainder.  It prints an error message if there
are not exactly 3 arguments, if the second is not +, -, x, or /,
if the first or third arguments are not valid Roman numerals
(upper case only), or if the result can not be represented as
a Roman numeral in the range I (1) to MMMCMXCIX (3999).

An integer in the range 1 to 3999 is represented as a Roman numeral
by replacing the four decimal digits with strings from each of the
four columns of Table 1.  (0 is the empty string).  For example,
2048 = "MM" + "" + "XL + "VIII" = MMXLVIII.

  Digit  1000  100   10    1
  -----  ----  ----  ----  ----
      0
      1   M     C     X     I
      2   MM    CC    XX    II
      3   MMM   CCC   XXX   III
      4         CD    XL    IV
      5         D     L     V
      6         DC    LX    VI
      7         DCC   LXX   VII
      8         DCCC  LXXX  VIII
      9         CM    XC    IX

  Table 1.  Roman numeral conversion.


DESIGN

The program uses a class Roman, which represents a Roman numeral
with the following interface:

  Roman a=n;     // Convert int n (1 to 3999) to a Roman, a
  Roman b(s);    // Convert const char* s ("I" to "MMMCMXCIX") to Roman, b
  Roman::bad x;  // Exception thrown for an invalid constructor argument
  x.what()       // An error message as a string
  int(a)         // Returns the value as an int (1 to 3999)
  a.toString()   // Returns the value as a string ("I" to "MMMCMXCIX")

Conversion to int may be implicit.  For example

  try {
    Roman a("XIV"), b(32);
    cout << int(a);    // 16
    cout << b.toString(); // XXXII
    cout a+b;  // 48
  }
  catch (Roman::bad e) {
    cout << "Error: " << e.what << endl;
  }

The value is represented as an int, n.  To convert to string, the
4 decimal digits of n (obtained by repeated division by 10 and taking
the remainder) are used to select strings from table 1, which are
concatenated.

To convert a string to int, the characters from the input string are
processed one at a time by the following state machine.  The state
represents the last input: M, D, C, L, X, V, I, or other.

  State  Input  ||  Action     Next state
  -----  -----  ||  ------     ----------
  Start  any    ||  n = 0      next char
  M      any    ||  n += 1000  next char
  D      any    ||  n += 500   next char
  C      M, D   ||  n -= 100   next char
         other  ||  n += 100   next char
  L      any    ||  n += 50    next char
  X      C, L   ||  n -= 10    next char
         other  ||  n += 10    next char
  V      any    ||  n += 5     next char
  I      V, X   ||  n -= 1     next char
         other  ||  n += 1     next char
  other         ||  Accept     Stop

The state machine depends on the presence of a terminating character
which is not from the set M, D, C, L, X, V, or I.  For a const char*
(but not a string), this will normally be '\0'.

The machine accepts any string whether it is a valid Roman numeral
or not.  To check if it is valid, it is converted back to a string
and compared with the original input.  For example, the state machine
accepts "MIDDLE" as 2051, but this converts back to "MMLI", so this
would throw Roman::bad.

To compile: g++ roman.cpp
*/

#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;

// Roman numeral
class Roman {
  int n;  // Always 1 to 3999
public:
  class bad: public domain_error { // Thrown by e.g. Roman("foo") or Roman(-1)
  public:
    bad(const string& s=""): domain_error(s) {}
  };
  Roman(int i);            // e.g. Roman(16), must be 1 to 3999
  Roman(const char* s);    // e.g. Roman("XVI") is 16
  string toString() const;          // e.g. returns "XVI"
  operator int() const {return n;}  // e.g. returns 16
};

// Convert i to Roman, must be 1 to 3999
Roman::Roman(int i): n(i) {
  if (n<1 || n>3999)
    throw bad("Not I to MMMCMXCIX (1 to 3999)");
}

// Convert s to Roman, must be a valid Roman numeral
Roman::Roman(const char* s): n(0) {
  const char* p=s;
  while (*p) {
    if (*p=='M')
      n += 1000;
    else if (*p=='D')
      n += 500;
    else if (*p=='C') {
      if (p[1]=='D' || p[1]=='M')
        n -= 100;
      else
        n += 100;
    }
    else if (*p=='L')
      n += 50;
    else if (*p=='X') {
      if (p[1]=='L' || p[1]=='C')
        n -= 10;
      else
        n += 10;
    }
    else if (*p=='V')
      n += 5;
    else if (*p=='I') {
      if (p[1]=='V' || p[1]=='X')
        n -= 1;
      else
        n += 1;
    }
    else
      break;
    ++p;
  }
  if (n<1 || n>3999)
    throw bad(string("Not 1 to 3999: ") + s);
  if (s != toString())
    throw bad(string(s) + " should be " + toString());
}

// Convert n to string
string Roman::toString() const {
  static const char* t[10][4] = {  // t[x][i] is i'th digit x as Roman
    {"",   "",    "",    ""},
    {"M",  "C",   "X",   "I"},
    {"MM", "CC",  "XX",  "II"},
    {"MMM","CCC", "XXX", "III"},
    {"",   "CD",  "XL",  "IV"},
    {"",   "D",   "L",   "V"},
    {"",   "DC",  "LX",  "VI"},
    {"",   "DCC", "LXX", "VII"},
    {"",   "DCCC","LXXX","VIII"},
    {"",   "CM",  "XC",  "IX"}};
  int x=n;
  string s="";  // result
  for (int i=3; i>=0 && x>0; --i) {
    s = t[x%10][i] + s;
    x /= 10;
  }
  return s;
}

// Calcuate, e.g. roman XI + CV prints CXVI
int main(int argc, char** argv) {

  // Check for 3 arguments
  if (argc != 4) {
    cout << "Usage: roman X + V\n"
      "  where X and V are Roman numerals (I to MMMCMXCIX)"
      " and + is one of +,-,x,/\n";
    return 1;
  }

  // Calculate
  try {
    Roman a(argv[1]), b(argv[3]);
    switch (argv[2][0]) {
      case '+': a=a+b; break;
      case '-': a=a-b; break;
      case 'x': a=a*b; break;
      case '/': a=a/b; break;
      default: throw Roman::bad(argv[2]);
    }
    cout << a.toString() << endl;
  }
  catch (Roman::bad x) {
    cout << "Invalid expression: " << x.what() << endl;
  }
  return 0;
}