In my previous post, I explained an s-expression-like language that handles die rolls mixed with arithmetic, and how to generate an abstract syntax tree for it. In this continued tutorial we’re going to create the evaluator in python. In the end we should have something that works like this:

>>> evaluate(['+', ['*', 2.0, ['/', 10.0, 2.0]], 3.0])
13.0

This is fairly simple: given an expression, apply the operator to the parameters of the expression. If a parameter is its own sub-expression, evaluate it first.

 1 def evaluate(tree):
 2     if tree:
 3         if type(tree) == float:
 4             return tree
 5         elif tree[0] == '+':
 6             return evaluate(tree[1]) + evaluate(tree[2])
 7         elif tree[0] == '-':
 8             return evaluate(tree[1]) - evaluate(tree[2])
 9         elif tree[0] == '*':
10             return evaluate(tree[1]) * evaluate(tree[2])
11         elif tree[0] == '/':
12             return evaluate(tree[1]) / evaluate(tree[2])
13         elif tree[0] == 'd':
14             count = int(evaluate(tree[1]))
15             sides = int(evaluate(tree[2]))
16             return float(sum(random.randint(1, sides) for x in range(count)))

Trying it out shows that it works perfectly.

>>> evaluate(['/', ['d', 2.0, ['*', 14.0, 2.0]], 3.0])
5.0

We can go from a string to a result with our s-expression language. Next we’ll do it with the more familiar infix notation. We have covered the process already—all that is different is the grammar. With our s-expression language, order of operations is unambiguous. With infix, we need an explicit order of operations: parenthesis, roll dice, multiply/divide, add/subtract. Each level in this order will have its own grammar rule, with lower-precedence rules containing references to higher-precedence rules. A rule for operators that are associative (or left-grouping) look like this:

a : b ( ('+'|'-') b)* ;

Visually:

grammar rule for an associative infix operator

In this example, a has a higher precedence than b. Rules for operators that aren’t associative and don’t have a left-grouping or right-grouping rule, look similar:

a : b ('d' b)? ;

Visually:

grammar rule for a non-associative infix operator

The last rule will look like this, where a is the first rule:

z : '(' a ')' | number ;

Visually:

final infix rule

Using our small set of operators, then, we get this grammar:

a : b ( ('+'|'-') b )*;
b : c ( ('*'|'/') c )*;
c : z ( 'd' z )?;
z : '(' a ')' | number;
number : ('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')+;

The names aren’t very descriptive, and since we know that in the first rule the bs are terms of the addition or subtraction, instead of b we can call it term. We can apply the same kind of thinking across the grammar and end up with a more descriptive version:

expression : term ( ('+'|'-') term )*;
term : factor ( ('*'|'/') factor )* ;
factor : rollterm ( 'd' rollterm )?;
rollterm : '(' expression ')' | number;
number : ('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')+;

We already know the techniques to make a parser. The associative rule ( a : b ( ('+'|'-') b)* ; ) method looks like this:

1 def a(self):
2     ast = self.term()
3     while self.peek() and self.peek() in '+-'
4         operator = self.pop()
5         ast = [operator, ast, self.b()]
6     return ast

Notice on line 5 the operator goes first. This is because we want the result of parsing 1+2-3 to look like ['-', ['+', 1.0, 2.0], 3.0] instead of [[1.0, '+', 2.0], '-', 3.0] .

If we create each rule this way, the code ends up like this:

 1 class DiceParser(object):
 2     def __init__(self, expr):
 3         token_pattern = r'(\d+|\s+|[-+*/d()])'
 4         if re.match('^%s*$' % token_pattern, expr):
 5             match = re.findall(token_pattern, expr)
 6             self.tokens = [x for x in match if x and not x.isspace()]
 7         else:
 8             raise RuntimeError("Failed to tokenize expression '%s'" % expr)
 9 
10     def pop(self):
11         return self.tokens.pop(0) if self.tokens else None
12 
13     def peek(self):
14         return self.tokens[0] if self.tokens else None
15 
16     def parse(self):
17         ast = self.expression()
18         if self.peek():
19             raise RuntimeError("expected end of expression")
20         return ast
21 
22     def expression(self):
23         ast = self.term()
24         while self.peek() and self.peek() in '+-':
25             operator = self.pop()
26             ast = [operator, ast, self.term()]
27         return ast
28 
29     def term(self):
30         ast = self.factor()
31         while self.peek() and self.peek() in '*/':
32             operator = self.pop()
33             ast = [operator, ast, self.factor()]
34         return ast
35 
36     def factor(self):
37         ast = self.rollterm()
38         if self.peek() and self.peek() == 'd':
39             self.pop() # 'd'
40             ast = ['d', ast, self.rollterm()]
41         return ast
42 
43     def rollterm(self):
44         if self.peek() and self.peek() == '(':
45             self.pop() # '('
46             ast = self.expression()
47             if self.pop() != ')':
48                 raise RuntimeError("expected ')'")
49             return ast
50         elif self.peek().isdigit():
51             return self.number()
52         else:
53             raise RuntimeError("expected number or '('")
54 
55     def number(self):
56         if self.peek().isdigit():
57             return float(self.pop())
58         else:
59             raise RuntimeError("expected number")

The method at line 16 is necessary. Without it, a valid expression followed by incorrect syntax would get discarded without throwing an error. Test it out using the evaluate function defined before.

>>> DiceParser("2d(14*2)/3").parse()
['/', ['d', 2.0, ['*', 14.0, 2.0]], 3.0]
>>> evaluate(DiceParser("2d(14*2)/3").parse())
12.0

I’d venture to say you now have a more sophisticated and useful dice calculator than 90% of dice calculators available. Extending the grammar to include different types of mathematical operators is trivial. Feel free to use this code without credit, and please use it in your role-playing game software.