7
\$\begingroup\$

I'm designing a new esoteric language, and the interpreter is in Python3. It is going to use Prefix Notation, so as part of the interpreter, I need a function that evaluates a string as prefix notation and returns a number. Here is my code so far:

import re
import math

class Operator:
    def __init__(self, arity, function):
        self.arity = arity
        self.function = function

    def __call__(self, *args):
        assert(len(args) == self.arity)
        return self.function(*args)

operatorTable = { "+": Operator(2, lambda a,b: a+b),
             "-": Operator(2, lambda a,b: a-b),
             "/": Operator(2, lambda a,b: a/b),
             "*": Operator(2, lambda a,b: a*b),
             "<": Operator(2, lambda a,b: a<b),
             ">": Operator(2, lambda a,b: a>b),
             "_": Operator(1, lambda a: -a),
             "p": Operator(0, lambda: math.pi),
             "e": Operator(0, lambda: math.e)
}

def prefixParse(code):
    if code[0] in operatorTable:
        operator = operatorTable[code[0]]

        if operator.arity == 2:
            arg1, chomp1 = prefixParse(code[1:])
            arg2, chomp2 = prefixParse(code[chomp1 + 1:])
            return operator(arg1, arg2), chomp1 + chomp2 + 1

        elif operator.arity == 1:
            arg, chomp = prefixParse(code[1:])
            return operator(arg), chomp + 1

        elif operator.arity == 0:
            return operator(), 1

    match = re.match("^\d+", code)
    if match:
        return int(match.group(0)), match.end()

    if code[0] == ' ':
        res = prefixParse(code[1:])
        return res[0], res[1] + 1

print(prefixParse("+2*5 10")[0])

I'm interested in hearing any improvements you have to offer, but I'm particularly interested in these design questions:

  • Is the recursive prefixParse a good/suitable algorithm for parsing prefix notation, or is there a simpler way to do it?

  • Is it overkill to use the Operator class?

  • Is there a way to "chomp" the string in place rather than handing a bunch of string indices back and forth? That would be nice because then to get an integer result from the parse function, I don't have to do prefixParse(code)[0] which looks kinda ugly IMO.

  • Is the layout of the multi-line operatorTable assignment good code formatting?

\$\endgroup\$
6
\$\begingroup\$

Only addressing your last point about the layout of operatorTable, i would use 4 space indentation as according to PEP8-indentation.

operatorTable = { 
    "+": Operator(2, lambda a,b: a+b),
    "-": Operator(2, lambda a,b: a-b),
    "/": Operator(2, lambda a,b: a/b),
    "*": Operator(2, lambda a,b: a*b),
    "<": Operator(2, lambda a,b: a<b),
    ">": Operator(2, lambda a,b: a>b),
    "_": Operator(1, lambda a: -a),
    "p": Operator(0, lambda: math.pi),
    "e": Operator(0, lambda: math.e),
}

Also note the comma after the last item. This has a small advantage when you use a source control system, when another item is added after the last item only the new line will show up in a diff and not the previous line which only has a comma added.

\$\endgroup\$
  • \$\begingroup\$ Ooh, nice point about the source control! \$\endgroup\$ – DJMcMayhem May 17 '18 at 17:03
6
\$\begingroup\$

General comment

Your code is well organised and easy to follow. Still it would be nice to add a bit of documentation, for instance to describe what the functions return. Also, you could try to follow PEP8, the Style Guide for Python Code, for instance, by using snake_case rather than camelCase. Also, I'd try to align the content of operatorTable to get something like:

operatorTable = {
    "+": Operator(2, lambda a,b: a+b),
    "-": Operator(2, lambda a,b: a-b),
    "/": Operator(2, lambda a,b: a/b),
    "*": Operator(2, lambda a,b: a*b),
    "<": Operator(2, lambda a,b: a<b),
    ">": Operator(2, lambda a,b: a>b),
    "_": Operator(1, lambda a: -a),
    "p": Operator(0, lambda: math.pi),
    "e": Operator(0, lambda: math.e)
}

The Operator class

I quite like the Operator class and the way you use it to map characters to function objects.

However, the various lambda functions you are defining are not need as you could use functions from the operator module.

Also, you could define a class to handle the special case of constants to avoid defining dummy functions.

You'd get something like:

class Operator:
    def __init__(self, arity, function):
        self.arity = arity
        self.function = function

    def __call__(self, *args):
        assert(len(args) == self.arity)
        return self.function(*args)

class Constant:
    def __init__(self, value):
        self.value = value
        self.arity = 0

    def __call__(self, *args):
        assert(len(args) == self.arity)
        return self.value

operatorTable = {
    "+": Operator(2, operator.add),
    "-": Operator(2, operator.sub),
    "/": Operator(2, operator.truediv),
    "*": Operator(2, operator.mul),
    "<": Operator(2, operator.lt),
    ">": Operator(2, operator.gt),
    "_": Operator(1, operator.neg),
    "p": Constant(math.pi),
    "e": Constant(math.e),
}

Parsing

Instead of relying on a recursion function progressing one digit at a time, you could split your input into tokens (numbers and operators in your case) and then iterate over the different tokens.

I'd suggest something like (but it can probably be done in a better way):

def tokenize(string):
    while string:
        c = string[0]
        if c in operatorTable:
            yield operatorTable[c]
            string = string[1:]
        elif c in whitespaces:
            string = string[1:]
        else:
            match = re.match("^\d+", string)
            if match:
                yield Constant(int(match.group(0)))
                string = string[match.end():]
            else:
                raise ValueError("Could not parse " + string)

To be continued.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.