import java.util.Scanner;

public class Interpreter {
	public static final int NOP = 0;
	public static final int ADD = 1;
	public static final int SUB = 2;
	public static final int MUL = 3;
	public static final int MOD = 4;
	public static final int LDI = 5;
	public static final int LDS = 6;
	public static final int STS = 7;
	public static final int JUMP = 8;
	public static final int JE = 9;
	public static final int JNE = 10;
	public static final int JLT = 11;
	public static final int IN = 12;
	public static final int OUT = 13;
	public static final int CALL = 14;
	public static final int RETURN = 15;
	public static final int HALT = 16;
	public static final int ALLOC = 17;

	static void error(String message) {
		throw new RuntimeException(message);
	}

	public static String readProgramConsole() {
		@SuppressWarnings("resource")
		Scanner sin = new Scanner(System.in);
		StringBuilder builder = new StringBuilder();
		while (true) {
			String nextLine = sin.nextLine();
			if (nextLine.equals("")) {
				nextLine = sin.nextLine();
				if (nextLine.equals(""))
					break;
			}
			if (nextLine.startsWith("//"))
				continue;
			builder.append(nextLine);
			builder.append('\n');
		}
		return builder.toString();
	}

	/*********************/
	/** IMPLEMENTIERUNG **/
	/*********************/
	
	
	private static int[] stack = new int[128];

	private static int stackPointer = -1;
	private static int framePointer = -1;
	

	public static void main(String[] args) {
		System.out.println("Eingabe:");
		int[] cmds = parse(readProgramConsole());
		System.out.println(execute(cmds));
	}
	
	/* PUSH UND POP: */
	
	public static int pop() {
		if (stackPointer < 0)
			error("Ungültiges Programm. Kann nichts vom leeren Stack entnehmen.");
		return stack[stackPointer--]; // Stack-Pointer wird nach der Benutzung um 1 reduziert
	}

	public static void push(int value) {
		if (stackPointer >= stack.length-1)
			error("Ungültiges Programm. Der Stack ist voll.");
		stack[++stackPointer] = value; // Stack-Pointer wird vor der Benutzung um 1 erhöht
	}

	
	/* PARSE UND HILFSMETHODEN: */
	
	public static int[] parse(String textProgram) {
		// Array über eingegebene Zeilen (ohne Leerzeilen)
		String[] lines = textProgram.split("\n");
		
		// Rückgabearray
		int[] cmd = new int[lines.length];
		
		// Durchlaufe alle Zeilen und wandle Instruktionen in Zahlenwerte um.
		// Prüfe währenddessen auf fehlerhafte Eingaben. Leerzeichen werden
		// ebenfalls als fehlerhaft gewertet, also z. B. "ADD " wäre hier falsch.
		for (int i = 0; i < lines.length; i++) {
			String[] words = lines[i].split(" ");  // darf nicht "" (Leerzeile) sein
			
			switch (words[0]) {
				case "NOP":
					cmd[i] = checkCmd(NOP, words); break;
				case "ADD":
					cmd[i] = checkCmd(ADD, words); break;
				case "SUB":
					cmd[i] = checkCmd(SUB, words); break;
				case "MUL":
					cmd[i] = checkCmd(MUL, words); break;
				case "MOD":
					cmd[i] = checkCmd(MOD, words); break;
				case "LDI":
					cmd[i] = checkCmdImmLab(LDI, words, lines); break;
				case "LDS":
					cmd[i] = checkCmdImmLab(LDS, words, lines); break;
				case "STS":
					cmd[i] = checkCmdImmLab(STS, words, lines); break;
				case "JUMP":
					cmd[i] = checkCmdImmLab(JUMP, words, lines); break;
				case "JE":
					cmd[i] = checkCmdImmLab(JE, words, lines); break;
				case "JNE":
					cmd[i] = checkCmdImmLab(JNE, words, lines); break;
				case "JLT":
					cmd[i] = checkCmdImmLab(JLT, words, lines); break;
				case "CALL":
					cmd[i] = checkCmdImm(CALL, words); break;
				case "RETURN":
					cmd[i] = checkCmdImm(RETURN, words); break;
				case "IN":
					cmd[i] = checkCmd(IN, words); break;
				case "OUT":
					cmd[i] = checkCmd(OUT, words); break;
				case "HALT":
					cmd[i] = checkCmd(HALT, words); break;
				case "ALLOC":
					cmd[i] = checkCmdImm(ALLOC, words); break;
				default:  // sollte ein Label sein, sonst ungültig
					cmd[i] = checkLabel(words);
			}
		}
		
		return cmd;
	}
	
	private static int checkCmd(int cmd, String[] words) {
		if (words.length != 1) 
			error("'" + words[0] + "' must not have any arguments, but was '" + String.join(" ", words) + "'");
		return cmd << 16;
	}
	
	private static int checkCmdImm(int cmd, String[] words) {
		if (words.length != 2 || !words[1].matches("^-?\\d+$"))
			error("'" + words[0] + "' must be followed by a single integer, but was '" + String.join(" ", words) + "'");
		// Grundsätzlich: cmd << 16 (Befehl nach links geshiftet), dann: + immediate
		// Das funktioniert jedoch nur für positive Zahlen, welche man einfach addieren kann,
		// negative muss man aber richtig schneiden (unteren 16 Bit), da z. B. -1 binär nur
		// aus 1ern besteht. Um die unteren/rechten 16 Bit einer Zahl zu bekommen und die
		// oberen auf 0 zu setzen kann man 0xFFFF verwenden (binäres Und).
		// Anstelle des + kann man auch das binäre Oder verwenden (sicherer für Überläufe)
		return cmd << 16 | Integer.parseInt(words[1]) & 0xFFFF;
	}
	
	private static int checkCmdImmLab(int cmd, String[] words, String[] lines) {
		if (words.length != 2)
			error("'" + words[0] + "' must be followed by a single argument, but was '" + String.join(" ", words) + "'");
		
		if (words[1].matches("^-?\\d+$")) // ist Zahl
			return cmd << 16 | Integer.parseInt(words[1]) & 0xFFFF;
		else // ist Label? -> finden!
			for (int i = 0; i < lines.length; i++)
				if (lines[i].matches("^" + words[1] + ":$"))
					return cmd << 16 | i & 0xFFFF;
		
		error("The label '" + words[1] + "' could not be found for command '" + words[0] + "'");
		return -1;  // unreachable
	}
	
	private static int checkLabel(String[] words) {
		if (words.length != 1 || words[0].charAt(words[0].length()-1) != ':')  // kann kein Label sein
			error("Invalid statement '" + String.join(" ", words) + "'");
		
		String label = words[0].substring(0, words[0].length()-1);
		
		// Label darf nicht leer sein
		if (label.length() == 0)
			error("The empty string is not a valid label");
		
		// Label darf nicht nur aus Zahlen bestehen:
		if (!label.matches(".*[a-zA-Z].*"))
			error("Labels must contain at least one letter, but was '" + label + "'");
		
		return NOP << 16;
	}

	
	/* EXECUTE: */
	
	public static int execute(int[] program) {	
		int programCounter = 0;
		
		while (true) {			
			if (programCounter < 0 || programCounter >= program.length)
				error("Das Programm ist ungültig. Die Instruktion am Index " + programCounter + " existiert nicht.");
			
			int opCode = program[programCounter] >> 16;  // wieder die vorderen 16 Bit bekommen
			int imm = program[programCounter] << 16 >> 16;
			// oder z. B.:
			//int imm = program[programCounter] & 0xFFFF;  // nur die hinteren 16 Bit (Immediate mit 16 0-Bits vorne)
			//if (imm >> 15 == 1) {  // 16. Bit gesetzt
			//	imm |= 0xFFFF0000;  // mit 1ern auffüllen
			//}
			
			switch (opCode) {
				case NOP:
					break;
				case ADD:
					push(pop() + pop());  // (o1 + o2) als Ergebnis auf den Stack legen
					break;
				case SUB:
					push(pop() - pop()); 
					break;
				case MUL:
					push(pop() * pop());
					break;
				case MOD:
					push(pop() % pop());
					break;
				case LDI:
					push(imm);  // für negative Zahlen nicht nötig (wenndann aber normal mit 1ern auffüllen)
					break;
				case LDS:
					push(stack[framePointer + imm]);
					break;
				case STS:
					stack[framePointer + imm] = pop();
					break;
				case JUMP:
					programCounter = imm;  // negative Werte sollten irgendwie im Error enden (tut es dann)
					continue;  // um den Program-Counter nicht noch zu erhöhen (wie es der Normalfall ist)
				case JE:
					if (pop() == pop()) {
						programCounter = imm;
						continue;  // kein break, sondern direkt weiter ohne PC zu erhöhen
					} break;
				case JNE:
					if (pop() != pop()) {
						programCounter = imm;
						continue;
						
					} break;
				case JLT:
					if (pop() < pop()) {
						programCounter = imm;
						continue;
					} break;
				case IN:
					push(MiniJava.read());
					break;
				case OUT:
					MiniJava.write(pop());
					break;
				case CALL:
					int newProgramCounter = pop();  // Adresse der aufgerufenen Funktion
					
					// Argumente konsumieren / zwischenspeichern
					int[] args = new int[imm];
					for (int i = 0; i < imm; i++)
						args[i] = pop();
					
					// FP und PC sichern
					push(framePointer);
					push(programCounter+1);
					
					// Argumente wieder pushen (Reihenfolge beachten!)
					for (int i = imm-1; i >= 0; i--)
						push(args[i]);
					
					// FP und PC ändern
					programCounter = newProgramCounter;
					framePointer = stackPointer;  // = alter SP - Funk.addr. + gesicherter PC/FP
					
					continue;  // PC nicht noch erhöhen
				case RETURN:
					int ret = pop();  // Rückgabewert ganz oben
					
					for (int i = 0; i < imm; i++)  // Params + Vars entfernen
						pop();  // einfach verwerfen
					
					// PC + FP wiederherstellen
					programCounter = pop();
					framePointer = pop();

					push(ret);  // Rückgabewert wieder oben ablegen
					continue;
				case HALT:
					return pop();
				case ALLOC:
					stackPointer += imm;
					break;
			}
			
			programCounter++; // zum nächsten Befehl gehen
		}
	}
}