Problem:

C: 短絡評価

問題

直大くんと北大くんはゲームをしています。
北大くんは、まず以下の BNF で表される論理式を生成します。

<formula>  ::= <or-expr>
<or-expr>  ::= <and-expr>
             | <or-expr> "|" <and-expr>
<and-expr> ::= <term>
             | <and-expr> "&" <term>
<term>     ::= "(" <or-expr> ")" | "?"

& は論理積を、| は論理和を表し、& の方が | より先に評価されます。

直大くんは、この論理式を（文字列として見て）左から読んでいき、? を見つけたとき以下の行動をします。

その ? を 0 にしても 1 にしても論理式の評価結果が変わらないことが確定しているなら、何もせず読み進める。

そうでないなら、北大くんに 1 円払い、その ? を 0 または 1 に書き換える。

論理式は以下のように評価されます。いわゆる普通の論理式です。

(0 & ?) == 0
(1 & 0) == 0
(1 & 1) == 1
(0 | 0) == 0
(0 | 1) == 1
(1 | ?) == 1

直大くんが論理式の評価結果を確定させるために支払う必要がある最小金額はいくらでしょう？ 評価結果を 0 にする場合と 1 にする場合でそれぞれ求めてください。

入力形式

上の BNF に従う論理式が一行で与えられます。

制約

論理式の長さは 2\times 10^5 を超えない。

出力形式

評価結果を 0、1 にするために必要な最小金額を空白区切りで出力してください。

入力例1

?&?|?&?|?&?

出力例1

3 2

0 にしたい場合は 0 0 0 で書き換えて 0&?|0&?|0&? とし、
1 にしたい場合は 1 1 で書き換えて 1&1|?&?|?&? とするのが最適です。

入力例2

?&?&?|?&?&?

出力例2

2 3

それぞれ 0&?&?|0&?&?、1&1&1|?&?&? となります。

入力例3

(?|?|?)&?&?&?&?|?&?|?&?

出力例3

4 4



Sample input:
?&?|?&?|?&?


Sample output:
3 2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
question = 1
AND = -1
OR = -2
left = -3
right = -4

tr = {'?': 1, '&': -1, '|': -2, '(': -3, ')': -4}

def evalor(L):
    if len(L) == 1:
        return L[0]
    x0, x1 = L[0]
    for i in range(1, len(L)):
        y0, y1 = L[i]
        x0, x1 = x0 + y0, min(x1, x0 + y1)
    return (x0, x1)

def push(f, s):
    if f and f[-1] == (AND, AND):
        f.pop()
        p = f.pop()
        return push(f, andeval(p, s))
    else:
        f.append(s)
        return f

def andeval(p, s):
    x0, x1 = p
    y0, y1 = s
    return (min(x0, x1 + y0), x1 + y1)
    

S = [tr[s] for s in input().strip()]
f = []
for s in S:
    if s == question:
        f = push(f, (s, s))
    elif s == AND or s == left:
        f.append((s, s))
    elif s == right:
        stack = []
        while f[-1] != (left, left):
            sp = f.pop()
            assert sp[0] > 0 and sp[1] > 0
            stack.append(sp)
        assert f.pop() == (left, left)
        push(f, evalor(stack[::-1]))
f = evalor(f)
print(*f)

Submission status: Accepted

Solution code:
# from inspect import currentframe
# from sys import exit, stderr


# debug function
# def debug(*args):
#     names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
#     print(', '.join(names.get(id(arg),'???') + str(id(arg)) +' = '+repr(arg) for arg in args), file=stderr)


src = list(str(input()))
tokens = [tok for tok in src if tok != " "]
# debug(tokens)

# "" as EOF
tokens.append("")
cur = 0
def parse_formula():
    return parse_or()

def parse_or():
    global cur
    lhs = parse_and()
    if tokens[cur] == "|":
        cur += 1
        rhs = parse_or()
        zero = lhs[0] + rhs[0]
        one = min(lhs[1], lhs[0] + rhs[1])
        return (zero, one)
    return lhs

def parse_and():
    global cur
    lhs = parse_term()
    if tokens[cur] == "&":
        cur += 1
        rhs = parse_and()
        zero = min(lhs[0], lhs[1] + rhs[0])
        one = lhs[1] + rhs[1]
        return (zero, one)
    return lhs

def parse_term():
    global cur
    if tokens[cur] == "?":
        cur += 1
        # debug(cur, 1)
        return [1, 1]
    elif tokens[cur] == "(":
        cur += 1
        # debug(cur, "or")
        res = parse_or()
        if tokens[cur] != ")":
            raise Exception("not closed")
        cur += 1
        # debug(cur)
        return res
ans = parse_formula()
print(ans[0], ans[1])
# debug(cur)
# print(len(tokens))