calcurate expression including fixed-length integer, add, substruct with sed

adder-with-sed.py

# coding:utf-8
"""
usage: python adder-with-sed.py <max_num_digits> <max_num_terms>
   $ echo '55+77-250+442' | sed -E -f <(python adder-with-sed.py 5 5)
     => 324
"""
from collections import defaultdict

def sed_adjust_digits(digits):
    """
    すべての数値の桁数をdigit桁に揃える。足りない場合は0で埋める。

    IN:  "123+45+6"
    OUT: "000123+000045+000006"
    """
    print(r's/([0-9]{{1,}})/{zeros}\1/g'.format(zeros='0'*digits)) # すべての項の先頭にdigits分の0を付与する
    print(r's/0*([0-9]{{{digits}}})/\1/g'.format(digits=digits))  # すべての項の下位digits桁より上を削除

def sed_convert_10_complement(digits, prefix):
    """
    指定されたprefixに続くdigit桁の数値を、10の補数に置換するsedスクリプトを表示する。

    IN:  "prefix_12345"
    OUT: "prefix_87655"
    """
    # 与えられた数に対して10の補数を取るには、桁ごとに9から引いた値を作り、それに1を加算すればよい。
    for d in reversed(range(digits)):
        dl = d
        dr = digits-d-1
        for n in range(10):
            print(r's/{prefix}([0-9]{{{dl}}}{n}[0-9]{{{dr}}}):?/\1\2:{m}/'.format(digits=digits, dl=dl, dr=dr, n=n, m=9-n, prefix=prefix))
    print(r's/{prefix}([0-9]{{{digits}}}):([0-9]{{{digits}}})/\1\3/'.format(digits=digits, prefix=prefix))
    print(r's/{prefix}([0-9]{{{digits}}})/\1[\2@0@{zeros}1]/'.format(digits=digits, zeros='0'*(digits-1), prefix=prefix))
    sed_invert_digits(digits, prefix=r'(@)')
    sed_solve_internal_add(digits)

    print(r's/{prefix}([0-9]{{{digits}}})/\1\2/'.format(digits=digits, prefix=prefix))

def sed_convert_plus_to_internal_add(digits):
    """
    足し算の式のうち先頭の2項を、加算の内部表現に変換するsedスクリプトを表示する。

    IN:  "123+345+678"
    OUT: "[123@0@543]+678"
    """
    print(r's/^([0-9]{{{digits}}})\+([0-9]{{{digits}}})/[\1@0@\2]/'.format(
        digits=digits,
        ))
    sed_invert_digits(digits, prefix=r'(@)')

def sed_invert_digits(digits, prefix):
    for i in range(int(digits/2)):
        print(r's/{prefix}([0-9]{{{n}}})([0-9])([0-9]*)([0-9])([0-9]{{{n}}})\]/\1\2\5\4\3\6]/'.format(n=i,prefix=prefix))

def sed_solve_internal_add(digits):
    """
    内部表現で表された加算を行うsedスクリプトを表示する。

    IN:  "[123@0@543]"
    OUT: "468"

    "...X@Z@Y...|" 部分に対して、X+Y+Zの一の位Aと、十の位Bを求め、
    "...@B@...|A" に置換する。 (X,Y,Aは1桁の数字、Z,Bは0または1)
    これを桁数分繰り返すことで、最終的に
    "[@0@]..."  のような形式になり、"..." の部分に足し算の答えが入る。

    例: 123 + 789
    IN     "[123@0@987]"
    step1: "[12@1@87]2"
    step2: "[1@1@7]12"
    step3: "[@0@]912"
    OUT:   "912"

    最後に "[@0@]" が残るパターンと "[@1@]" が残るパターンがある。
    前者は最上位桁の繰り上がりなしの場合で、後者は最上位桁の繰り上がりがあった場合(オーバーフロー)である。

    正規表現でX+Y+Zを計算することはできないので、すべてのX,Y,Zの組に対してパターンを作って列挙する。
        例: (X,Y,Z)=(7,8,1),(A,B)=(6,1) の場合、 "s/(7@1@8)([0-9]*)\|/@1@\2]6"
    X,Y,Z の組は [0-9]*[0-9]*[01] で162通りあるが、 OUTとなる A,B の組は [0-9]*[01] の18通りしかないので、
    同じA,BとなるX,Y,Zのパターンを|で繋いでまとめることで、実際にOUTするsedコマンドの行数は18個に抑えることができる。
    """
    table = defaultdict(list)
    for x in range(10):
        for y in range(10):
            for z in (0,1):
                a = (x+y+z)%10
                b = int((x+y+z)/10)
                table[(a,b)].append((x,y,z))

    for i in range(digits):
        for ab,xyz_list in sorted(table.iteritems()):
            print(r's/\[([0-9]*)({xzy_list})([0-9]*)\]/\[\1@{b}@\3]{a}/'.format(
                a=ab[0],
                b=ab[1],
                xzy_list='|'.join('{}@{}@{}'.format(x,z,y) for x,y,z in sorted(xyz_list))
                ))

    print(r's/\[@[01]@\]//')

def sed_format(digits):
    """
    出力用の整形を行うsedスクリプトを表示する。
    * 負のレンジの値に対して、10の補数を取って負の符号を付ける。
    * 先頭の不要なゼロを除去する
    """
    print(r's/^([5-9])/-\1/')
    sed_convert_10_complement(digits, '^(-)'.format(digits=digits))
    print(r's/^(-?)0{{1,{digits_m1}}}/\1/'.format(digits_m1=digits-1))

def script(digits, terms):
    """
    加算を減算を含む数式を計算するsedスクリプトを表示する。

    式は [0-9]{1,digits}([-+][0-9]{1,digits}){0,terms-1} で表される必要がある。
    ここでdigits,termsは自然数であり、それぞれ最大桁数、最大項数である。
    出力されるsedスクリプトのサイズは、おおむね digits*terms の値によって決まる。

    表現できる数値の範囲は
        -5*10^(digits-1) 〜 5*10^(digits-1)-1
    であり、この範囲を超えるとオーバーフローする。
    たとえばdigits=5の場合、49999+1 を計算すると -50000 となる。

    IN:  10-15+8+9
    OUT: 12
    """
    sed_adjust_digits(digits)
    for j in range(terms-1):

        # 減算を加算で置き換える。
        sed_convert_10_complement(digits, r'^([0-9]{{{digits}}}-)'.format(digits=digits))
        print(r's/^([0-9]{{{digits}}})-/\1+/'.format(digits=digits))

        sed_convert_plus_to_internal_add(digits)
        sed_solve_internal_add(digits)
    sed_format(digits)

import sys
digits,terms = [int(x) for x in sys.argv[1:3]]
script(digits,terms)