AoC 2020 D18: Operation Order

| Problem statement | Source code | Tags: Parsing

← Previous Back to AoC Index Next →

OK, I cheated for this one. Python already has ast; I just need to hack it to get the right precedence. Turns out that I can just replace the operators with some other ones. For part 1, replacing + with / would put it at the same precedence as *. For part 2, replacing + with ** would put it at higher precedence than *.

Once I have the tree with the correct precedence, I evaluate it recursively using a visitor.

class ExprEvaluator(ast.NodeVisitor):
    def visit_Expression(self, node):
        return self.visit(node.body)

    def visit_BinOp(self, node):
        if type(node.op) == ast.Mult:
            return self.visit(node.left) * self.visit(node.right)
        elif type(node.op) == ast.Add:
            return self.visit(node.left) + self.visit(node.right)
        elif type(node.op) == ast.Div:
            return self.visit(node.left) + self.visit(node.right)
        elif type(node.op) == ast.Pow:
            return self.visit(node.left) + self.visit(node.right)

    def visit_Constant(self, node):
        return node.value

Of course I could have built an actual recursive descent parser, but this was way easier and is what nature intended for AoC purposes—language choices reward simple solutions.

← Previous Back to AoC Index Next →