summaryrefslogtreecommitdiff
path: root/18_2020.py
blob: 0a15aeb8c19ecbe3818a822a9c797c68f4c10d35 (plain)
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import fileinput
import re

# Term := LIT | \( EMul \)
# EAdd := Term (+ Term)*
# EMul := EAdd (\* EAdd)*


def Term(W, i):
    if W[i] == "(":
        v, i2 = EMul(W, i + 1)
        assert W[i2] == ")", W[i2]
        return (v, i2 + 1)
    else:
        return (int(W[i]), i + 1)


def EAdd(W, i):
    t1, i2 = Term(W, i)
    ans = t1

    while True:
        if i2 == len(W) or W[i2] == ")" or W[i2] == "*":
            return ans, i2
        else:
            assert W[i2] == "+"
            t2, i3 = Term(W, i2 + 1)
            ans = ans + t2
            i2 = i3


def EMul(W, i):
    t1, i2 = EAdd(W, i)
    ans = t1
    while True:
        if i2 == len(W) or W[i2] == ")":
            return ans, i2
        else:
            assert W[i2] == "*"
            t2, i3 = EAdd(W, i2 + 1)
            ans = ans * t2
            i2 = i3


# TermP1 := LIT | \( EXPR \)
# Expr := TermP1 (OP TermP1)*

# Each line can be parsed as an Expr


# Gives you back the value of the term and the *next* word to parse
def TermP1(W, i):
    if W[i] == "(":
        v, i2 = Expr(W, i + 1)
        assert W[i2] == ")", W[i2]
        return (v, i2 + 1)
    else:
        return (int(W[i]), i + 1)


def eval1(first, op, second):
    if op == "+":
        return first + second
    else:
        assert op == "*"
        return first * second


# evaluate expression starting at W[i] until ')' or end
def Expr(W, i):
    t1, i2 = TermP1(W, i)
    ans = t1

    while True:
        if i2 == len(W) or W[i2] == ")":
            return ans, i2
        else:
            assert W[i2] in ["+", "*"], W[i2]
            t2, i3 = TermP1(W, i2 + 1)
            ans = eval1(ans, W[i2], t2)
            i2 = i3


def solve(p1):
    ans = 0
    L = list([l.strip() for l in fileinput.input()])
    for l in L:
        l = l.replace("(", "( ")
        l = l.replace(")", " )")
        words = l.split()
        v, idx = (Expr if p1 else EMul)(words, 0)
        ans += v
        assert idx == len(words)
    return ans


print(solve(True))
print(solve(False))