122 lines
3.1 KiB
Python
122 lines
3.1 KiB
Python
# https://www.codewars.com/kata/58924f2ca8c628f21a0001a1/
|
|
from enum import Enum, auto
|
|
from dataclasses import dataclass
|
|
|
|
|
|
class OpKind(Enum):
|
|
LEFT = "<"
|
|
RIGHT = ">"
|
|
INC = "+"
|
|
DEC = "-"
|
|
INPT = ","
|
|
OUTP = "."
|
|
JMPZ = "["
|
|
JMPNZ = "]"
|
|
|
|
|
|
@dataclass
|
|
class Opcode:
|
|
kind: OpKind
|
|
operand: int = 1
|
|
|
|
|
|
def stream_tokens(code) -> Opcode:
|
|
for c in code:
|
|
try:
|
|
yield Opcode(OpKind(c))
|
|
except ValueError:
|
|
continue
|
|
|
|
|
|
def optimize(tokens):
|
|
new_tokens = opti_collapse_tokens(tokens)
|
|
if len(new_tokens) <= 1:
|
|
return new_tokens
|
|
|
|
tokens = otpi_cancel_opposing(new_tokens)
|
|
while len(new_tokens := otpi_cancel_opposing(tokens)) != len(tokens):
|
|
tokens = new_tokens
|
|
|
|
return tokens
|
|
|
|
|
|
def opti_collapse_tokens(tokens):
|
|
# collapse consecutive identical tokens
|
|
new_tokens = []
|
|
for next_token in tokens:
|
|
if new_tokens == []: # init stack
|
|
new_tokens.append(next_token)
|
|
continue
|
|
current_token = new_tokens.pop()
|
|
if (
|
|
current_token.kind == next_token.kind
|
|
and str(current_token.kind.value) in "<>+-"
|
|
):
|
|
current_token.operand += 1
|
|
new_tokens.append(current_token)
|
|
else:
|
|
new_tokens.append(current_token)
|
|
new_tokens.append(next_token)
|
|
return new_tokens
|
|
|
|
|
|
def otpi_cancel_opposing(tokens):
|
|
# cancel opposing adjacent tokens
|
|
new_tokens = []
|
|
for next_token in tokens:
|
|
if new_tokens == []: # init stack
|
|
new_tokens.append(next_token)
|
|
continue
|
|
current_token = new_tokens.pop()
|
|
if (
|
|
current_token.kind.value + next_token.kind.value
|
|
in ("+-", "-+", "<>", "><", "[]")
|
|
and current_token.operand == next_token.operand
|
|
):
|
|
continue
|
|
else:
|
|
new_tokens.append(current_token)
|
|
new_tokens.append(next_token)
|
|
return new_tokens
|
|
|
|
|
|
def generate_code(tokens):
|
|
out = []
|
|
nest = 0
|
|
# code generation
|
|
for token in tokens:
|
|
match token.kind:
|
|
case OpKind.LEFT:
|
|
out.append(f"{' ' * nest * 2}p -= {token.operand};\n")
|
|
case OpKind.RIGHT:
|
|
out.append(f"{' ' * nest * 2}p += {token.operand};\n")
|
|
case OpKind.INC:
|
|
out.append(f"{' ' * nest * 2}*p += {token.operand};\n")
|
|
case OpKind.DEC:
|
|
out.append(f"{' ' * nest * 2}*p -= {token.operand};\n")
|
|
case OpKind.INPT:
|
|
out.append(f"{' ' * nest * 2}*p = getchar();\n")
|
|
case OpKind.OUTP:
|
|
out.append(f"{' ' * nest * 2}putchar(*p);\n")
|
|
case OpKind.JMPZ:
|
|
out.append(f"{' ' * nest * 2}" + "if (*p) do {\n")
|
|
nest += 1
|
|
case OpKind.JMPNZ:
|
|
nest -= 1
|
|
out.append(f"{' ' * nest * 2}" + "} while (*p);\n")
|
|
|
|
if nest < 0:
|
|
return "Error!"
|
|
|
|
if nest != 0:
|
|
return "Error!"
|
|
|
|
return "".join(out)
|
|
|
|
|
|
def brainfuck_to_c(source_code):
|
|
s = stream_tokens(source_code)
|
|
tokens = optimize(s)
|
|
code = generate_code(tokens)
|
|
return code
|