Hide

Problem D
BASIC Interpreter

The BASIC computer programming language has been popular for many years, and there have been dozens of ‘dialects’ of the language. It’s considered a high-level language and is typically interpreted (rather than compiled). For this problem, write an interpreter for a restricted dialect of BASIC. Here is a description of the language.

Each input line contains one statement. Each statement begins with a non-negative integer, which we will call its label. Following the label is a single space and one of the following commands (with explanations following):

  • LET X = <ARITHMETIC_STATEMENT>
    Assign the result of the arithmetic statement to variable X.

  • IF <CONDITION> THEN GOTO L
    If the boolean given is true, then go to the statement labeled L, where L is a valid label. (If the condition is not true, continue execution to the statement with the next lowest label.)

  • PRINT <PRINT_STATEMENT>
    Produce output, without an appended newline.

  • PRINTLN <PRINT_STATEMENT>
    Produce output, with an appended newline.

Here are details on types, variables, and the terms <ARITHMETIC_STATEMENT>, <CONDITION>, and <PRINT_STATEMENT> used above.

  • All numeric values (in the input and for the variable representation) are signed 32-bit integers.

  • All variables are single uppercase characters (A through Z). They are all global in scope, and are all initialized to zero before program execution begins.

  • <ARITHMETIC_STATEMENT> is one of the following: X, X + Y, X - Y, X * Y, or X / Y. Here, X and Y each indicate either a variable or an integer.

  • <CONDITION> is one of the following: X = Y, X > Y, X < Y, X <> Y, X <= Y, or X >= Y. Again, X and Y each indicate either a variable or an integer. Here, <> indicates inequality.

  • <PRINT_STATEMENT> is either a variable name or a literal string delimited by double quotes. Inside the quotes, the string contains only alphanumeric characters (a-z, A-Z, 0-9) and spaces.

In the signed 32-bit arithmetic, the usual rules of truncation towards zero (for division) and overflow (for addition and multiplication) and underflow (for subtraction) apply. The following examples illustrate these conditions:

5 / 2           = 2                  65536 * 32768   = -2147483648
-1 / 2          = 0                  -65536 * 32768  = -2147483648
2147483647 + 1  = -2147483648        -2147483648 * 2 = 0
-2147483648 - 1 = 2147483647         2147483647 * 2  = -2

Further, division by zero will not occur.

Program execution begins with the statement having the smallest label, and proceeds with the statement having the next smallest label. (Unless a GOTO executes, in which case execution proceeds at the designated label.) The program halts after it has completed the statement with the largest label (which is guaranteed not to contain a GOTO).

Input

Input consists of a single program. Each line contains a single valid statement. Each pair of adjacent tokens in the input is separated by a single space. Integers in the input will all be in the range $-2^{31}$ to $2^{31}-1$. Input ends at end of file.

Output

Give the output (PRINT and PRINTLN statements) of the input program when it is executed.

Sample Input 1 Sample Output 1
10 LET A = 1
20 PRINT "HELLO THERE "
30 PRINTLN A
40 LET A = A + 1
50 IF A <= 5 THEN GOTO 20
60 PRINTLN "DONE"
HELLO THERE 1
HELLO THERE 2
HELLO THERE 3
HELLO THERE 4
HELLO THERE 5
DONE
Sample Input 2 Sample Output 2
40 PRINT P
180 PRINTLN "DONE"
130 PRINTLN " IS PRIME"
60 LET X = D * D
80 LET R = P / D
100 LET R = P - R
20 LET D = 1
140 IF 1 = 1 THEN GOTO 180
30 LET P = 111
150 PRINTLN " IS NOT PRIME"
170 PRINTLN " IS A DIVISOR"
50 LET D = D + 1
70 IF P < X THEN GOTO 130
120 IF 1 = 1 THEN GOTO 50
90 LET R = R * D
110 IF R = 0 THEN GOTO 150
10 PRINTLN "PRIME TESTER"
160 PRINT D
PRIME TESTER
111 IS NOT PRIME
3 IS A DIVISOR
DONE

Please log in to submit a solution to this problem

Log in