AOJ 2401: Equation

恒等式を判定する問題。普通は構文解析するのだろうが、置換とevalで乗り切った。

問題はこちら。

問題

ある論理式が与えられる。式の中には変数がいくつかあるが、この変数の真偽に関係なく論理式が常に成り立つかどうか、つまり恒等式であるかどうかを答えよ。

解法

無理やりevalで評価できる形に変換していく。

厄介なのが論理包含で、これは a -> b という式があった時、aが真でbが偽のときのみ偽で、それ以外は真となるような演算子である。言い換えると a != 1 or b となる。

変数は最大でも11個しかないので総当たりで式の評価をしていく。a,b,c,,,への代入は明示的にしなければならず、 for a,b,c,,, in itertools.product(["1","0"],repeat=11) というふうにしてもevalでの評価に反映されないので注意。

T,F = True,False
while 1:
    s = raw_input()
    if s == "#": break
    for i in xrange(100): s = s.replace("--","")
    for b,a in zip(["=","->","-","*","+"],[") == ("," != 1 or "," not "," and "," or "]):
        s = s.replace(b,a)
    s = "("+s+")"
    for v in xrange(2**11):
        a,b,c,d,e,f,g,h,i,j,k = map(int,list(format(v,"b").zfill(11)))
        if not eval(s):
            print "NO"
            break
    else:
        print "YES"