21308번 - Ternary Machine 다국어

A ternary numerical system (also called base 3) has three as its base. Just as a binary digit is called a bit in base 2, a ternary digit is surprisingly called a trit. The trits are 0, 1 and 2. For this problem, you will write an interpreter for a ternary machine that accepts as input a program consisting of a string of trits and executes it. Instructions for this machine consist of an opcode sometimes followed by a parameter. The opcodes for the machine follow. S1 and S2 refer to the item at the top of the stack and the 2nd item on the stack respectively. When these are used below, it implies they are removed from the stack for the given instruction (popped).

The machine you will implement must support a stack of precisely 1024 items. Items can only be Values or characters. The memory heap is of arbitrary size, and possibly sparse. Addresses used to reference the heap are positive Values.

Number is a decimal integer from 1 to 31 bits in length. (Yes, it’s in bits not trits.) The end of the value is indicated by the trit 2. Ex. 100112 = 19 (decimal).

Value is a signed Number. Since Number is no more than 31 bits, a Value can be represented using a 32-bit quantity (-2147483647 ≤ Value ≤ 2147483647).

Label is a string of 1 to 128 trits of value 0 or 1. Its end is always indicated by a trit of value 2. If an attempt is made to redefine a Label mark, that is a RUN-TIME ERROR.

Subroutines calls may be nested (and recursive) to a maximum depth of 1024 (the top-level execution depth is 0).

Any illegal character (non-trit) encountered during execution should cause a RUN-TIME ERROR.

Program execution starts with the first character in the program and continues until the opcode 222 is reached or there is a RUN-TIME ERROR.

Input consists of one or more lines. The first line contains a string of up to 8192 characters representing the program to execute (the terminating line feed is not part of the program to execute). If the program requires input (for opcodes 1210 and 1211), the input follows after the first line (after the line feed), on one or more lines as required by the program. If a program requires input, there will always be enough input supplied. Care should be taken when implementing the 1210 and 1211 opcodes so as to not consume too much input. Ex. For opcode 1211, only an optional leading minus sign and decimal digits should be read until a non-decimal digit is reached.

The output consists of at least one line which is the output of the supplied ternary program and/or the message “RUN-TIME ERROR” if an error occurred during execution of the ternary program. Some possible RUN-TIME ERRORs include invalid character, invalid opcode, stack underflow, stack overflow, division by 0, undefined label, etc. If a RUN-TIME ERROR does occur, be sure to flush all pending output from the ternary program prior to printing RUN-TIME ERROR. Attempting to access an address in the machine’s heap that has not been previously set should retrieve a value of 0 – this is not a RUN-TIME error.

Note: It is possible that the ternary program will generate some output and then get a RUN-TIME ERROR. It is also possible that there are potential errors in the ternary program but these errors will not be reached during execution (ex. invalid character/opcode, missing label, redefined label, etc.). In this case, these RUN-TIME ERRORs will not be reported (which is correct).