about summary refs log tree commit diff
path: root/scratch/facebook/language.py
blob: b57f469b49d20214ce9d0c8e1e6e4870b55458f6 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import random

# Write an evaluator for a small language:
#   - operators: '+', '*'
#   - operands:  Integers
#
# E.g. evaluate("2+14*90+5*16")

def tokenize(xs):
    result = []
    i = 0
    while i < len(xs):
        current = xs[i]
        if current in {'*', '+'}:
            result.append(current)
            i += 1
            continue
        elif current == ' ':
            i += 1
            continue
        else:
            i += 1
            while i < len(xs) and xs[i] in {str(x) for x in range(10)}:
                current += xs[i]
                i += 1
            result.append(int(current))
    return result

def ast(tokens):
    result = []
    series = []
    for token in tokens:
        if token == '+':
            result.append(series)
            series = []
        elif token == '*':
            continue
        else:
            series.append(token)
    if series:
        result.append(series)
    return result

def product(xs):
    result = 1
    for x in xs:
        result *= x
    return result

def evaluate(x):
    tokens = tokenize(x)
    tree = ast(tokens)
    return sum([product(xs) for xs in tree])

n = 7
operands = [random.randint(0, 100) for _ in range(n)]
operators = [random.choice(['+','*']) for _ in range(n - 1)]
expr = []
for i in range(n - 1):
    expr.append(operands[i])
    expr.append(operators[i])
expr.append(operands[-1])

expr = ' '.join([str(x) for x in expr])
print("Expression: {}".format(expr))
print("Tokens: {}".format(tokenize(expr)))
print("AST: {}".format(ast(tokenize(expr))))
print("Answer: {}".format(evaluate(expr)))
assert evaluate(expr) == eval(expr)
print("Success!")