문제

아이디어

난해한 프로그래밍 언어로 유명한 BrainFuck을 해석하는 문제다.

입력을 보면 숨이 턱 막히지만 하나씩 구현하다 보면 특별히 어려운 문제는 아니었다.

나는 다음과 같은 순서로 BrainFuck을 해석했다.

코드 컴파일

명령어를 우선 하나의 문자열로 받아와, 컴파일을 해준다.
이 단계에서는 스택을 활용하여 대괄호 쌍의 위치를 파악해주고, HashMap 자료구조에 저장해줬다.
컴파일 과정에서 스택 언더플로우가 발생하거나, 컴파일이 완료되었을 때 스택이 비어있지 않다면 컴파일 에러로 간주한다.

명령어 실행

이 단계에서는 컴파일이 끝난 명령어 문자열을 차례로 실행해주면 된다.
주어진 조건을 맞춰 그대로 작성해준다면 문제 없이 구현할 수 있다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int T;
    static int[] byteArray;
    static int pointer;
    static String inst;
    static int index;
    static HashMap<Integer, Integer> bracket;

    static void incPointer() {
        if (pointer == 32767) pointer = 0;
        else pointer++;
    }

    static void decPointer() {
        if (pointer == 0) pointer = 32767;
        else pointer--;
    }

    static void addValue() {
        if (byteArray[pointer] == 255) byteArray[pointer] = 0;
        else byteArray[pointer]++;
    }

    static void subValue() {
        if (byteArray[pointer] == 0) byteArray[pointer] = 255;
        else byteArray[pointer]--;
    }

    static void print() throws IOException {
        bw.write((char) byteArray[pointer]);
    }

    static void frontBracket() {
        if (byteArray[pointer] == 0) index = bracket.get(index);
    }

    static void backBracket() {
        if (byteArray[pointer] != 0) index = bracket.get(index);
    }

    static boolean compile() {
        bracket = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < inst.length(); i++) {
            char c = inst.charAt(i);
            if (c == '[') stack.push(i);
            else if (c == ']') {
                if (stack.isEmpty()) return false;
                int frontBracket = stack.pop();
                bracket.put(frontBracket, i);
                bracket.put(i, frontBracket);
            }
        }
        return stack.isEmpty();
    }

    static void comment() {
        while (inst.charAt(index) != 'N') index++;
    }

    static void brainFuck() throws IOException {
        StringBuilder instBuilder = new StringBuilder();
        String temp = "";
        while (!(temp = br.readLine()).equals("end")) {
            instBuilder.append(temp).append("N");
        }

        inst = instBuilder.toString();
        if (!compile()) {
            bw.write("COMPILE ERROR");
            return;
        }

        for (index = 0; index < inst.length(); index++) {
            char c = inst.charAt(index);
            switch (c) {
                case '>' -> incPointer();
                case '<' -> decPointer();
                case '+' -> addValue();
                case '-' -> subValue();
                case '.' -> print();
                case '[' -> frontBracket();
                case ']' -> backBracket();
                case '%' -> comment();
            }
        }

    }

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
            byteArray = new int[32768];
            pointer = 0;
            bw.write("PROGRAM #" + i + ":\n");
            brainFuck();
            bw.write('\n');
        }
        bw.flush();
    }
}

채점 결과

화살표를 사용하는 Switch문을 옛날 버전 Java에는 지원되지 않는 걸로 알아서 Java 15로 제출했다.
Java 11로도 제출해봤지만 역시나 컴파일 에러. Java 12부터 지원되는 문법이라고 한다.