postscript.py

#!/usr/bin/env python3


def eval(instructions: list):
    stack = []
    mem = {}
    exec = list(reversed(instructions))
    binary_ops = {
        "add": lambda v1, v2: v1 + v2,
        "sub": lambda v1, v2: v1 - v2,
        "mul": lambda v1, v2: v1 * v2,
        "div": lambda v1, v2: v1 / v2,
        "gt": lambda v1, v2: v1 > v2,
        "lt": lambda v1, v2: v1 < v2,
        "gte": lambda v1, v2: v1 >= v2,
        "lte": lambda v1, v2: v1 <= v2,
        "eq": lambda v1, v2: v1 == v2,
    }

    def run(val):
        if isinstance(val, list):
            exec.extend(list(reversed(val)))
        else:
            stack.append(val)

    while len(exec) > 0:
        instr = exec.pop()
        if isinstance(instr, str):
            if instr in binary_ops:
                v2 = stack.pop()
                v1 = stack.pop()
                stack.append(binary_ops[instr](v1, v2))
            elif instr == "dup":
                stack.append(stack[-1])
            elif instr == "exch":
                stack[-1], stack[-2] = stack[-2], stack[-1]
            elif instr == "def":
                value = stack.pop()
                key = stack.pop()
                mem[key] = value
            elif instr == "if":
                iftrue = stack.pop()
                cond = stack.pop()
                if cond:
                    run(iftrue)
            elif instr == "ifelse":
                iffalse = stack.pop()
                iftrue = stack.pop()
                cond = stack.pop()
                if cond:
                    run(iftrue)
                else:
                    run(iffalse)
            elif instr.startswith("/"):
                stack.append(instr[1:])
            else:
                run(mem[instr])
        else:
            stack.append(instr)

    return stack.pop()


def read(input: str) -> list:
    ret = [[]]
    tokens = input.replace("{", " { ").replace("}", " } ").split()
    for token in tokens:
        if str.isdigit(token):
            ret[-1].append(int(token))
        elif token == "{":
            ret.append([])
        elif token == "}":
            arr = ret.pop()
            ret[-1].append(arr)
        else:
            ret[-1].append(token)
    return ret[-1]


def read_eval(input: str):
    return eval(read(input))


def test(fn, arg, expected):
    actual = fn(arg)
    if actual != expected:
        print("Arg:      ", arg)
        print("Expected: ", expected)
        print("Actual:   ", actual)
        exit(1)


# Part 1: Building an RPN Calculator
# 1. Take a list of instructions, push each instruction onto a stack, return the top element of the stack
# 2. If the instruction is the string 'add', pop the last 2 elements off the stack and add them.  Push the result on the stack.
# 3. Add the remaining math instructions in a similar manner:
#   mul: [v1, v2, 'sub'] => push(v1 * v2)
#   sub: [v1, v2, 'sub'] => push(v1 - v2)
#   div: [v1, v2, 'div'] => push(v1 / v2)
# 4. Add the following stack instructions
#   dup:  duplicate the top element of the stack
#   exch: swap the top two elements of the stack
# 5. Add the following logic instructions
#   gt:  [v1, v2, 'gt']  => push(v1 > v2)
#   lt:  [v1, v2, 'lt']  => push(v1 < v2)
#   gte: [v1, v2, 'gte'] => push(v1 >= v2)
#   lte: [v1, v2, 'lte'] => push(v1 <= v2)

test(eval, [5, 4, 3], 3)

test(eval, [5, 4, "add"], 9)
test(eval, [5, 4, "sub"], 1)
test(eval, [5, 4, "add", 3, "sub"], 6)
test(eval, [5, 4, 3, "add", "mul"], 35)
test(eval, [12, 3, "div"], 4)

test(eval, [4, "dup", "mul"], 16)
test(eval, [4, 5, "exch", "sub"], 1)

test(eval, [5, 4, "gt"], True)
test(eval, [4, 5, "gt"], False)
test(eval, [5, 5, "gt"], False)
test(eval, [5, 4, "lte"], False)
test(eval, [4, 5, "lte"], True)
test(eval, [5, 5, "lte"], True)

# Part 2: Variables
# 6. When you see a string prefixed with '/', push the string onto the stack
# 7. Add the command 'def': pop the last 2 values off the stack, key and value.
#    Store the key and value in a dictionary representing memory
#    def: [key, value, 'def'] => mem[key] = value
# 8. When you see a string value, look it up in memory and push it onto the stack

test(eval, [5, 4, 3], 3)

test(eval, [5, 4, "add"], 9)
test(eval, [5, 4, "sub"], 1)
test(eval, [5, 4, "add", 3, "sub"], 6)
test(eval, [5, 4, 3, "add", "mul"], 35)
test(eval, [12, 3, "div"], 4)

test(eval, [4, "dup", "mul"], 16)
test(eval, [4, 5, "exch", "sub"], 1)

test(eval, [5, 4, "gt"], True)
test(eval, [4, 5, "gt"], False)
test(eval, [5, 5, "gt"], False)
test(eval, [5, 4, "lte"], False)
test(eval, [4, 5, "lte"], True)
test(eval, [5, 5, "lte"], True)

test(eval, ["/blah"], "blah")
test(eval, ["/x", 5, "def", 4, "x"], 5)

# Part 3: Simple Functions and conditionals
# 9. Ensure that arrays are pushed onto the stack verbatim
# 10. When retrieving a variable value, if it is an array, execute the instructions found in the array
# 11. Add the command if: [conditional, array, 'if'] => if(conditional) then run(array)
# 12. Add ifelse: [cond, iftrue, iffalse, 'ifelse'] => if(cond) then run(iftrue) else run(ifelse)

test(eval, [5, 4, 3], 3)

test(eval, [5, 4, "add"], 9)
test(eval, [5, 4, "sub"], 1)
test(eval, [5, 4, "add", 3, "sub"], 6)
test(eval, [5, 4, 3, "add", "mul"], 35)
test(eval, [12, 3, "div"], 4)

test(eval, [4, "dup", "mul"], 16)
test(eval, [4, 5, "exch", "sub"], 1)

test(eval, [5, 4, "gt"], True)
test(eval, [4, 5, "gt"], False)
test(eval, [5, 5, "gt"], False)
test(eval, [5, 4, "lte"], False)
test(eval, [4, 5, "lte"], True)
test(eval, [5, 5, "lte"], True)

test(eval, ["/blah"], "blah")
test(eval, ["/x", 5, "def", 4, "x"], 5)

test(eval, [5, [4, "/blah"]], [4, "/blah"])

test(eval, ["/sq", ["dup", "mul"], "def", 5, "sq"], 25)
test(eval, ["/test", [5, "eq", [10], "if"], "def", 5, "test"], 10)

test(
    eval,
    [
        "/fib",
        [
            "dup",
            1,
            "gt",
            [1, "sub", "dup", 1, "sub", "fib", "exch", "fib", "add"],
            "if",
        ],
        "def",
        11,
        "fib",
    ],
    89,
)

# Part 4: Reader
# 13. Add a read function that takes a string out outputs a list of tokens
# 14. Tokens are space separated. Integers should map to integers, everything else maps to strings.
# 15. Add support to read arrays.  Arrays are enclosed by brackets {}.  Spaces are not needed before and after brackets.

test(read, "5", [5])
test(read, "5 4 3", [5, 4, 3])
test(read, "5 4 3 abc /def", [5, 4, 3, "abc", "/def"])
test(read, "5 {4 3 2} 3", [5, [4, 3, 2], 3])

test(
    read_eval,
    """
/fib {dup 1 gt
        {1 sub dup 1 sub fib exch fib add
        } if
     } def
11 fib
""",
    89,
)

print("Success")