小町算(4)

7月20日の日記のパーサを少し書き直した。以下の点が改善された。

• komachi_parser.e()にlistとdequeのどちらでも渡せるようになった。
• komachi_parser.e()に渡したリストの値を破壊しない。
• インデックスを使うことによりパフォーマンスが少し改善された。
• 123を['1', '', '2', '', '3']のように扱えるようになった(但し、エラー処理を省略した)。

# komachi_parser.py
# -*- coding: utf-8 -*-

def e(L, idx=0):
    '+, -を処理'
    v1, idx = t(L, idx)
    while True:
        if idx < len(L) and (L[idx] == '+' or L[idx] == '-'):
            op = L[idx]
            idx += 1
            v2, idx = t(L, idx)
            if op == '+':
                val = v1 + v2
            elif op == '-':
                val = v1 - v2
            v1 = val
        else:
            break
    return v1

def t(L, idx):
    '*, /を処理'
    v1, idx = f(L, idx)
    while True:
        if idx < len(L) and (L[idx] == '*' or L[idx] == '/'):
            op = L[idx]
            idx += 1
            v2, idx = f(L, idx)
            if op == '*':
                val = v1 * v2
            elif op == '/':
                val = v1 / v2
            v1 = val
        else:
            break
    return v1, idx

def f(L, idx):
    '数値を処理'
    v1 = 0
    while True:
        if idx < len(L) and L[idx] == '':
            idx += 1
        elif idx < len(L) and L[idx].isdigit():
            v = L[idx]
            idx += 1
            v1 = v1 * 10 + int(v)
        else:
            break
    return v1, idx

if __name__ == '__main__':
    print e( ['1', '', '2', '', '3', '', '4', '-', '5', '*', '6', '/', '7', '-', '8', '*', '9'] )

import komachi_parser
import re, time

a = [['1']]
for n in map(str, range(2, 10)):
    b = []
    for s in a:
        for o in ['+', '-', '*', '/', '']:
            b.append(s + [o, n])
    a = b

t = time.time()
cnt = 0
for e in a:
    if komachi_parser.e(e) == 100:
        cnt += 1
print '%d pattern(s), %g sec' % (cnt, time.time() - t)
# 303 pattern(s), 13.032 sec

計算機方式？(+, -と*, /の優先順位を同じにしたバージョン)をまだ解いていないが、気が向いたらやるつもり。