21308번 Ternary Machine
문제
번역
롱——문제
3진수 프로그램을 해석하고 실행하는 인터프리터를 구현해야한다.
명령어는 고정된 형식이 존재하며 표를 참조한다.
올바르지 않은 입력에 대해서는 런타임에러를 출력하는데, 실행되지 않는 오류는 무시한다.
프로그램은 최대 8192자이며 입력이 필요한 경우 충분한 입력이 반드시 주어진다.
설계
구현문제로 보이는데 생각할 부분이 다소 많아보인다.
명령어 해석을 빠르게 처리해야하고
스택과 힙을 구현해야하겠고
예외처리도 해야하고…
주어진 것부터 묵묵히 하다보면 풀리겠지??
구현
1. 입출력과 기본함수
입력은 한번에 받아서 버퍼로 저장해둔다.
필요하면 버퍼에 하나씩 꺼내 쓰도록 하고
출력은 모아뒀다가 한번에 한다.
오류 출력시에는 기존 프로그램이 생성한 출력은 먼저 출력해야하는 것에 주의
isError = False
# 입력 버퍼 탐색 인덱스
buffer_index = 0
# 프로그램 탐색 인덱스
program_index = 0
# 명령어 사전
opcodes = [
# 4자리 명령부터 판단
# CODE | PARAM | DESCRIPTION
("1000", None, "ADD"),
("1001", None, "SUB"),
("1002", None, "MUL"),
("1010", None, "DIV"),
("1011", None, "MOD"),
("1200", None, "PRINT_CHAR"),
("1201", None, "PRINT_NUM"),
("1210", None, "READ_CHAR"),
("1211", None, "READ_NUM"),
("000", "number", "PUSH_POS"),
("001", "number", "PUSH_NEG"),
("020", None, "DUP"),
("021", None, "SWAP"),
("022", None, "DROP"),
("110", None, "STORE"),
("111", None, "LOAD"),
("200", "label", "LABEL"),
("201", "label", "CALL"),
("202", "label", "JUMP"),
("210", "label", "JUMP_IF_ZERO"),
("211", "label", "JUMP_IF_NEG"),
("212", None, "RETURN"),
("222", None, "HALT"),
]
stack = []
heap = {}
# 복귀 주소 스택
call_stack = []
# CALL, JUMP 등을 처리하기 위해 label 위치를 미리 매핑해야함
labels = {}
# 출력은 리스트에 모아두었다가 한 번에 출력
output = []
print(''.join(output), end='')
if isError:
print("RUN-TIME ERROR", end='')
한자리 숫자, 문자를 읽는 함수, 라벨을 읽는 함수, 프로그램 내 숫자를 읽는 함수가 필요하다.
스택에 넣는 부분이 많아서 그부분도 따로 함수로 뺀다.
# 버퍼에서 숫자 하나 읽어오는 함수
def read_number():
global buffer_index, isError
# 입력에 공백이 주어지나??
while buffer_index < len(input_buffer) and input_buffer[buffer_index].isspace():
buffer_index += 1
if buffer_index >= len(input_buffer):
isError = True
return 0
start = buffer_index
# 입력 값이 음수일 수 있음
if input_buffer[buffer_index] == '-':
buffer_index += 1
while buffer_index < len(input_buffer) and input_buffer[buffer_index].isdigit():
buffer_index += 1
if start == buffer_index or (input_buffer[start] == '-' and buffer_index == start + 1):
isError = True
return 0
return int(''.join(input_buffer[start:buffer_index]))
# 버퍼에서 문자 하나 읽어오는 함수
def read_char():
global buffer_index, isError
if buffer_index >= len(input_buffer):
isError = True
return 0
ch = input_buffer[buffer_index]
buffer_index += 1
return ord(ch)
# 프로그램에서 2로 끝나는 레이블을 읽어오는 함수
def read_label():
global program_index, isError
start = program_index
while program_index < len(program):
trit = program[program_index]
if trit == '2':
label = program[start:program_index]
program_index += 1
return label
elif trit not in '01':
isError = True
return None
program_index += 1
isError = True
return None
# 프로그램 내의 숫자 파싱하는 함수
def parse_number_program():
global program_index, isError
bits = []
count = 0
while program_index < len(program):
trit = program[program_index]
if trit == '0' or trit == '1':
bits.append(trit)
program_index += 1
count += 1
if count > 31:
isError = True
return 0
elif trit == '2':
program_index += 1
if not bits:
isError = True
return 0
return int(''.join(bits), 2)
else:
isError = True
return 0
isError = True
return 0
# 스택에 넣는 함수
def push_stack(value):
global stack, isError
if len(stack) >= 1024:
isError = True
return
stack.append(value)
# 콜스택에 넣는 함수
def push_call_stack(value):
global call_stack, isError
# 서브루틴도 1024 체크 필요
if len(call_stack) >= 1024:
isError = True
return
call_stack.append(value)
2. 레이블 스캔 함수
CALL이나 JUMP 명령 시 어디로 가야하는가?
그것을 미리 알기위해 레이블 스캔을 미리 진행한다.
실행 시 찾으려면 비효율적일 것 같아서리
섣불리 에러처리 해버리면 에러 전까지의 프로그램 아웃풋이 없으므로 주의해야한다.
# label 스캔하는 함수
def scan_labels():
global labels, isError
scan_index = 0
while scan_index < len(program):
# 트릿이 아니면 스캔 종료
if program[scan_index] not in '012':
break
matched = False
for code, param, description in opcodes:
if program.startswith(code, scan_index):
scan_index += len(code)
matched = True
# HALT 이후까지 스캔하면 불필요한 오류 발생 가능
if description == "HALT":
# return 해버리니 뒤쪽 레이블이 등록안됨...
break
elif description == "LABEL":
# label 읽기
start = scan_index
while scan_index < len(program):
trit = program[scan_index]
if trit == '2':
label = program[start:scan_index]
scan_index += 1
if not label or any(c not in '01' for c in label):
isError = True
return
if label in labels:
# 같은 위치에 중복된 레이블이면 허용
if labels[label] != scan_index:
isError = True
return
else:
# label 다음 위치
labels[label] = scan_index
break
elif trit not in '01':
isError = True
return
scan_index += 1
else:
# 끝까지 2를 못 만남
isError = True
return
# 숫자 건너뛰기
elif param == "number":
count = 0
while scan_index < len(program):
trit = program[scan_index]
scan_index += 1
if trit == '2':
break
elif trit not in '01':
isError = True
return
count += 1
if count > 31:
isError = True
return
# 레이블 건너뛰기
elif param == "label":
while scan_index < len(program):
trit = program[scan_index]
scan_index += 1
if trit == '2':
break
elif trit not in '01':
isError = True
return
# param 없는 경우
break
if not matched:
isError = True
break
return
3. 메인 루프
명령어 조건에 맞춰 메인 루프 작성
가장 단순하고 가장 별거없고 가장 노가다 구간
# 본 로직
while program_index < len(program) and not isError and not halted:
matched = False
for code, param, description in opcodes:
if program.startswith(code, program_index):
program_index += len(code)
matched = True
# 분기 시작
# ... 중략 ...
if not matched:
# 남은 코드가 공백이거나 무의미하면 무시하고 종료
if program_index >= len(program):
break
else:
isError = True
break
채점
반성
하필 또 파이썬이라 푸는데 엄청 오래 걸린 문제
구현만 잘하면 문제없을 줄 알았는데 생각보다 오류가 엄청났다.
레이블 스캔하는 부분에서 뜻대로 잘 동작하지 않아서 결과가 자꾸 틀어짐…
PyPy는 JIT 컴파일러가 있어서 더 빠르다고해서 Python3와 PyPy3 두개로 제출했다.
생각보다 시간 차이가 안나는데, 메모리는 당연히 PyPy3가 많이 쓸거고
속도는 연산자체가 그리 많은 문제가 아니라 큰 차이 안나는 것으로 보인다.
제한시간 빡빡한 문제에서 다시 한 번 비교해봐야할 듯
코드 확인