Skip to content

Instantly share code, notes, and snippets.

@kokumura
Last active Apr 27, 2017
Embed
What would you like to do?
calcurate expression including fixed-length integer, add, substruct with sed
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment