로마 숫자 후위 표기 계산기

헤르메스 포세이돈(HP)이 최신 기술로 새 계산기 HP CXX를 만들었다. 이 계산기는 I부터 MMMMCMXCIX까지의 정수에 대해 사칙연산을 지원한다.

이 문제에서는 HP CXX의 동작을 시뮬레이션한다. 입력의 각 줄은 다음 중 하나이다.

• I(1)부터 MMMMCMXCIX(4999)까지의 양의 정수를 나타내는 로마 숫자. 이 값을 가상 스택의 맨 위에 넣는다(push).
• 스택의 위쪽 두 값에 적용하는 사칙연산 기호 +, -, *, /.
• = 연산. 스택 맨 위의 값을 (로마 숫자로) 출력하라는 요청이다.

연산 규칙은 다음과 같다. 스택 맨 위의 값을 첫 번째 수, 그 바로 아래의 값을 두 번째 수라고 하자.

• +, *: (두 번째 + 첫 번째) 또는 (두 번째 × 첫 번째)를 스택에 넣는다.
• -: (두 번째 − 첫 번째)를 넣는다. 즉 두 번째 수에서 첫 번째 수를 뺀다.
• /: (두 번째 ÷ 첫 번째)를 정수 나눗셈으로 계산해 넣는다. 즉 두 번째 수를 첫 번째 수로 나눈다. 나누는 수(첫 번째 수)가 0이면 division by zero exception을 출력하고, 나뉘는 수(두 번째 수)만 스택에 다시 넣으며 나누는 수는 넣지 않는다.

연산을 요청했지만 스택에 수가 충분하지 않으면 stack underflow를 출력하고 스택을 그대로 둔다. 이는 이항 연산 + - * /와 출력 연산 = 모두에 적용된다.

=로 출력하려는 값이 0 이하이거나 MMMMCMXCIX(4999)보다 크면 out of range exception을 출력하고 다음 입력 줄로 넘어간다.

로마 숫자. 각 글자는 다음 값을 나타낸다.

글자를 나열하면 그 값을 더한다. 예를 들어 XXX = 10 + 10 + 10 = 30, LXI = 50 + 10 + 1 = 61이다. 작은 값이 큰 값 앞에 오면 대신 뺀다. 예를 들어 IV = 5 − 1 = 4, XC = 100 − 10 = 90이다. 다음 규칙을 따른다.

• M을 제외하고, 같은 글자를 네 번 이상 연달아 쓰지 않는다.
• 10의 거듭제곱(I, X, C)만 뺄 수 있다. 45는 VL이 아니라 XLV로 쓴다.
• 한 번에 한 글자만 뺀다. 8은 IIX가 아니라 VIII로, 19는 IXX가 아니라 XIX로 쓴다.
• 자기보다 10배를 초과하는 글자에서는 빼지 않는다. 즉 I는 V나 X에서만, X는 L이나 C에서만 뺄 수 있다(따라서 MIM은 잘못된 표기다).

입력의 각 줄은 다음 중 하나이다.

• I부터 MMMMCMXCIX까지의 로마 숫자, 또는
• 사칙연산 기호 +, -, *, /, 또는 출력 연산 =.

입력은 파일의 끝(EOF)에서 종료된다.

일이 일어나는 순서대로 한 줄씩 출력한다.

• 각 = 연산에 대해 스택 맨 위의 값을 로마 숫자로 출력한다.
• 오류가 발생하면 해당 메시지를 한 줄에 하나씩 출력한다.
  • division by zero exception
  • stack underflow
  • out of range exception

그 밖의 출력은 하지 않는다.