function tokenize(str)
    tokens = String[]
    token = ""
    for c in str
        if c == ' '
            token != "" && push!(tokens, token)
            token = ""
        elseif c == '+' || c == '*'
            token != "" && push!(tokens, token)
            push!(tokens, string(c))
        elseif c == '(' || c == ')'
            token != "" && push!(tokens, token)
            push!(tokens, string(c))
            token = ""
        else
            token *= c
        end
    end
    token != "" && push!(tokens, token)

    tokens
end

function part1(tokens::AbstractVector{<:AbstractString})
    n = 0
    op = +
    i = 1
    while i ≤ length(tokens)
        if tokens[i] == "("
            j, m = part1((@view tokens[i+1:end]))
            i += j + 1
            n = op(n, m)
        elseif tokens[i] == ")"
            break
        elseif tokens[i] == "+"
            op = +
            i += 1
        elseif tokens[i] == "*"
            op = *
            i += 1
        else
            n = op(n, parse(Int, tokens[i]))
            i += 1
        end
    end
    i, n
end
part1(str::AbstractString) = last(part1(tokenize(str)))

abstract type AbstractExpression end

mutable struct Expression <: AbstractExpression
    op::Function
    left::AbstractExpression
    right::AbstractExpression
end

mutable struct Value <: AbstractExpression
    val::Int
end

function parseexpr(tokens::AbstractVector{<:AbstractString})
    i, op, exp = 1, +, Value(0)
    while i ≤ length(tokens)
        if tokens[i] == "("
            j, right = parseexpr(@view tokens[i+1:end])
            i += j + 1
            if exp isa Value
                exp = Expression(op, exp, right)
            elseif op === +
                exp.right = Expression(op, exp.right, right)
            else
                exp = Expression(op, exp, right)
            end
        elseif tokens[i] == ")"
            break
        elseif tokens[i] == "+"
            op = +
            i += 1
        elseif tokens[i] == "*"
            op = *
            i += 1
        else
            leaf = Value(parse(Int, tokens[i]))
            if exp isa Value
                exp = Expression(op, exp, leaf)
            elseif op === +
                exp.right = Expression(op, exp.right, leaf)
            else
                exp = Expression(op, exp, leaf)
            end
            i += 1
        end
    end
    i, exp
end
parseexpr(str::AbstractString) = last(parseexpr(tokenize(str)))

evaluate(expr::Expression) = expr.op(evaluate(expr.left), evaluate(expr.right))
evaluate(expr::Value) = expr.val

part2(str::AbstractString) = evaluate(parseexpr(str))

let lines = readlines("input.txt")
    @info "Solution" sum(map(part1, lines)) sum(map(part2, lines))
end
