Problem:


Problem C: How can I satisfy thee? Let me count the ways...

Three-valued logic is a logic system that has, in addition to "true" and 
"false", "unknown" as a valid value.  

In the following, logical values "false", "unknown" and "true" are 
represented by 0, 1 and 2 respectively. 

Let "-" be a unary operator (i.e. a symbol representing one argument function) 
and let both "*" and "+" be binary operators (i.e. symbols representing 
two argument functions). 
These operators represent negation (NOT), conjunction (AND) and 
disjunction (OR) respectively. 
These operators in three-valued logic can be defined in Table C-1.

Table C-1: Truth tables of three-valued logic operators

-X(X*Y)(X+Y)

    
     

Let P, Q and R be variables ranging over three-valued logic values. 
For a given formula, you are asked to answer the number of triples (P,Q,R) 
that satisfy the formula, that is, those which make the value of the 
given formula 2. 
A formula is one of the following form (X and Y represent formulas). 

 Constants: 0, 1 or 2

 Variables: P, Q or R

 Negations: -X

 Conjunctions: (X*Y)

 Disjunctions: (X+Y)

Note that conjunctions and disjunctions of two formulas are always 
parenthesized. 

For example, when formula (P*Q) is given as an input, the value of 
this formula is 2 when and only when (P,Q,R) is (2,2,0), (2,2,1) or (2,2,2). 
Therefore, you should output 3. 

Input

The input consists of one or more lines. Each line contains a formula. 
A formula is a string which consists of 0, 1, 2, P, Q, R, -, *, +, (, ). 
Other characters such as spaces are not contained. 
The grammar of formulas is given by the following BNF. 

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

All the formulas obey this syntax and thus you do not have to care about 
grammatical errors.
Input lines never exceed 80 characters.  

Finally, a line which
contains only a "." (period) comes, indicating the end of the input.

Output

You should answer the number (in decimal) of triples (P,Q,R) that make the 
value of the given formula 2.  One line containing the number should be 
output for each of the formulas, and no other characters should be output.

Sample Input

(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.

Output for the Sample Input

3
11
0
27
0
7



Sample input:
(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.


Sample output:
3
11
0
27
0
7

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S_ = raw_input()
    if S_ == '.':
        break

    ans = 0
    for p, q, r in it.product([0, 1, 2], repeat = 3):
        S = S_
        S = S.replace("P", str(p)).replace("Q", str(q)).replace("R", str(r))

        for loop in range(100):
            S = S.replace("-0", "2")
            S = S.replace("-1", "1")
            S = S.replace("-2", "0")
            for a, b in it.product([0, 1, 2], repeat = 2):
                S = S.replace("(%d*%d)" % (a, b), str(min(a, b)))
                S = S.replace("(%d+%d)" % (a, b), str(max(a, b)))
            
        if S == "2":
            ans += 1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/python
class Ternary:
	def __init__(self,n): 
		self.n=n
	def __int__(self):
		return self.n
	def __neg__(self):
		return Ternary(2-int(self))
	def __mul__(self,o):
		return Ternary(min(int(self),int(o)))
	def __add__(self,o):
		return Ternary(max(int(self),int(o)))

import sys, itertools
from functools import reduce
R=[0,1,2]
while True:
	s=sys.stdin.readline().rstrip()
	if s=='.': break
	r=0
	for (a,b,c) in itertools.product(R,repeat=3):
		t=reduce(lambda t,e:t.replace(e[0],'Ternary(%d)'%e[1]),[['0',0],['1',1],['2',2],['P',a],['Q',b],['R',c]],s)
		if int(eval(t))==2: r+=1
	print(r)

Submission status: Accepted

Solution code:
# AOJ 1155: How can I satisfy thee? Let me count
# Python3 2018.7.17 bal4u

def term(idx):
    x, idx = factor(idx)
    op = buf[idx]
    y, idx = factor(idx+1);
    if op == '*':
        if x == 2 and y == 2: x = 2
        elif x == 0 or y == 0: x = 0
        else: x = 1
    else:
        if x == 0 and y == 0: x = 0
        elif x == 2 or y == 2: x = 2
        else: x = 1
    return [x, idx]

def factor(idx):
    global p, q, r
    if buf[idx] == '(': x, idx = term(idx+1)
    elif buf[idx] == '-':
        x, idx = factor(idx+1)
        x = 2-x; idx -= 1
    elif '0'<= buf[idx] <='9': x = int(buf[idx])
    elif buf[idx] == 'P': x = p
    elif buf[idx] == 'Q': x = q
    else: x = r
    return [x, idx+1]

while True:
    buf = list(input())
    if buf[0] == '.': break
    ans = 0
    for p in range(3):
        for q in range(3):
            for r in range(3):
                if factor(0)[0] == 2: ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import itertools as it
class mybool:
    def __init__(self, value):
        self.value = value
    def __neg__(self):
        return mybool(2-self.value)
    def __mul__(self, other):
        return mybool(min(self.value,other.value))
    def __add__(self, other):
        return mybool(max(self.value,other.value))

while 1:
    s = raw_input()
    if s == ".": break
    
    while "--" in s: s = s.replace("--","")
    s = s.replace("2","mybool(2)").replace("1","mybool(1)").replace("0","mybool(0)")
    
    ans = 0
    for p,q,r in it.product([0,1,2],repeat=3):
        P,Q,R = mybool(p),mybool(q),mybool(r)
        if eval(s).value == 2:
            ans += 1
    
    print ans

Submission status: Accepted

Solution code:
import itertools as it
class mybool:
    def __init__(self, value):
        self.value = value
    def __neg__(self):
        return mybool(2-self.value)
    def __mul__(self, other):
        return mybool(min(self.value,other.value))
    def __add__(self, other):
        return mybool(max(self.value,other.value))

while 1:
    s = raw_input()
    if s == ".": break

    for i in xrange(3):
        s = s.replace(str(i),"mybool(%d)"%i)
    
    ans = 0
    for p,q,r in it.product([0,1,2],repeat=3):
        P,Q,R = mybool(p),mybool(q),mybool(r)
        if eval(s).value == 2:
            ans += 1
    
    print ans

Submission status: Accepted

Solution code:
class F:
 __neg__=lambda s:F(2-s.v)
 __add__=lambda s,t:F(max(s.v, t.v))
 __mul__=lambda s,t:F(min(s.v, t.v))
 def __init__(s,v):s.v = v
import itertools as i,re
while 1:
 s=raw_input()
 if s==".":break
 s=re.sub("([0-R])","F(\\1)",s)
 print sum(eval(s).v==2 for P,Q,R in i.product([0,1,2],repeat=3))

Submission status: Accepted

Solution code:
def parser(left, right):
    if S[left] == '(' and S[right - 1] == ')':
        cnt = 0
        for i in range(left + 1, right - 1):
            if S[i] == '(':
                cnt += 1
            elif S[i] == ')':
                cnt -= 1
            elif cnt == 0 and S[i] == '+':
                return [max(x, y) for x, y in zip(parser(left + 1, i), parser(i + 1, right - 1))]
            elif cnt == 0 and S[i] == '*':
                return [min(x, y) for x, y in zip(parser(left + 1, i), parser(i + 1, right - 1))]
    elif S[left] == '-':
        return [2 - x for x in parser(left + 1, right)]
    elif S[left] == 'P':
        return [i // 9 % 3 for i in range(27)]
    elif S[left] == 'Q':
        return [i // 3 % 3 for i in range(27)]
    elif S[left] == 'R':
        return [i % 3 for i in range(27)]
    else:
        return [int(S[left]) for _ in range(27)]


while True:
    S = input()
    if S == '.':
        break
    print(parser(0, len(S)).count(2))

Submission status: Accepted

Solution code:
just_len = 60

import re
import collections

NUM     = r'(?P<NUM>\d+)'
PLUS    = r'(?P<PLUS>\+)'
MINUS   = r'(?P<MINUS>-)'
TIMES   = r'(?P<TIMES>\*)'
LPAREN  = r'(?P<LPAREN>\()'
RPAREN  = r'(?P<RPAREN>\))'
WS      = r'(?P<WS>\s+)'

master_pattern = re.compile('|'.join((NUM, PLUS, MINUS, TIMES, LPAREN, RPAREN, WS)))
Token = collections.namedtuple('Token', ['type', 'value'])


def generate_tokens(pattern, text):
    scanner = pattern.scanner(text)
    for m in iter(scanner.match, None):
        token = Token(m.lastgroup, m.group())

        if token.type != 'WS':
            yield token


def minus(x):
  if x==0: ans=2
  if x==1: ans=1
  if x==2: ans=0
  return ans

def mult(x,y):
  if x==0:
    a=0
  if x==1:
    if y==0: a=0
    if y==1: a=1
    if y==2: a=1
  if x==2:
    if y==0: a=0
    if y==1: a=1
    if y==2: a=2
  return a

def add(x,y):
  if x==0:
    if y==0: a=0
    if y==1: a=1
    if y==2: a=2
  if x==1:
    if y==0: a=1
    if y==1: a=1
    if y==2: a=2
  if x==2:
    a=2
  return a

class ExpressionEvaluator:
    def parse(self, text):
        self.tokens = generate_tokens(master_pattern, text)
        self.current_token = None
        self.next_token = None
        self._advance()

        # expr is the top level grammar. So we invoke that first.
        # it will invoke other function to consume tokens according to grammar rule.
        return self.expr()

    def _advance(self):
        self.current_token, self.next_token = self.next_token, next(self.tokens, None)

    def _accept(self, token_type):
        # if there is next token and token type matches
        if self.next_token and self.next_token.type == token_type:
            self._advance()
            return True
        else:
            return False

    def _expect(self, token_type):
        if not self._accept(token_type):
            raise SyntaxError('Expected ' + token_type)

    def expr(self):
        '''
        expression ::= term { ( +|-) term } *
        '''
        expr_value = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.current_token.type

            right = self.term()
            if op == 'PLUS':
                #expr_value += right
                expr_value = add(expr_value, right)
            elif op == 'MINUS':
                #expr_value -= right
                expr_value = add(expr_value, minus(right))
            else:
                raise SyntaxError('Should not arrive here ' + op)

        return expr_value

    def term(self):
        '''
        term    ::= factor { ('*') factor } *
        '''
        term_value = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.current_token.type

            if op == 'TIMES':
                #term_value *= self.factor()
                term_value = mult(term_value, self.factor())
            else:
                raise SyntaxError('Should not arrive here ' + op)

        return term_value

    def factor(self):
        '''
        factor  ::= NUM | (expr) | -(factor)

        '''

        # it can be a number
        if self._accept('NUM'):
            expr_value = int(self.current_token.value)
        # or (expr)
        elif self._accept('LPAREN'):
            expr_value = self.expr()
            self._expect('RPAREN')
        elif self._accept('MINUS'):
            expr_value = minus(self.factor())
        else:
            raise SyntaxError('Expect NUMBER or LPAREN')
        return expr_value


e = ExpressionEvaluator()
# print('parse 2'.ljust(just_len),
#       e.parse('2'))
#
# print('parse 2 + 3'.ljust(just_len),
#       e.parse('2 + 3'))
# print('parse 2 + 3 * 4'.ljust(just_len),
#       e.parse('2 + 3 * 4'))
#
# print('parse (2 + 3) * 4'.ljust(just_len),
#       e.parse('(2 + 3) * 4'))
while True:
  rS=input()
  if rS=='.': break

  ans=0
  for p in range(3):
    for q in range(3):
      for r in range(3):
        S = rS.replace('P',str(p))\
              .replace('Q',str(q))\
              .replace('R',str(r))
        if e.parse(S)==2: ans+=1
  print(ans)

Submission status: Accepted

Solution code:
import itertools


def parse(expr):
    if expr == "P":
        return lambda p, q, r: p
    if expr == "Q":
        return lambda p, q, r: q
    if expr == "R":
        return lambda p, q, r: r
    if expr == "0":
        return lambda p, q, r: 0
    if expr == "1":
        return lambda p, q, r: 1
    if expr == "2":
        return lambda p, q, r: 2
    if expr[0] == "-":
        t = parse(expr[1:])
        return lambda p, q, r: 2 - t(p, q, r)
    if expr[0] != "(" or expr[-1] != ")":
        raise SyntaxError("invalid syntax")
    depth = 0
    i = 1
    l = len(expr) - 1
    op_pos = -1
    while i < l:
        c = expr[i]
        if c == "(":
            depth += 1
        elif c == ")":
            depth -= 1
        elif depth == 0 and c in ("+", "*"):
            if op_pos != -1:
                raise SyntaxError("invalid syntax")
            op_pos = i
        i += 1
    if depth != 0 or op_pos == -1:
        raise SyntaxError("invalid syntax")
    op = {
        "+": lambda x, y: max(x, y),
        "*": lambda x, y: min(x, y)
    }[expr[op_pos]]
    lhs = parse(expr[1:op_pos])
    rhs = parse(expr[op_pos + 1:-1])
    return lambda p, q, r: op(lhs(p, q, r), rhs(p, q, r))


# first part
while True:
    line = raw_input()
    if line == ".":
        break
    ans = 0

    f = parse(line)
    for p, q, r in itertools.product((0, 1, 2), repeat=3):
        if f(p, q, r) == 2:
            ans += 1

    print ans

Submission status: Accepted

Solution code:
class N:
    def __init__(self, a):
        self.a = a

    def __mul__(self, b):
        if self.a == 0:
            return N(0)
        elif self.a == 1:
            return N((b.a >= 1) * 1)
        else:
            return b

    def __add__(self, b):
        if self.a == 0:
            return b
        elif self.a == 1:
            return N((b.a > 1) + 1)
        else:
            return N(2)

    def __neg__(self):
        if self.a == 2:
            return N(0)
        elif self.a == 1:
            return N(1)
        else:
            return N(2)

while True:
    s = input().replace("-", "-").replace("0", "N(0)").replace("1", "N(1)").replace("2", "N(2)")
    N(1) + N(2)
    if s == ".": break

    result = []
    for P in map(N, range(3)):
        for Q in map(N, range(3)):
            for R in map(N, range(3)):
                result.append(eval(s).a)
    print(result.count(2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import sys

sys.setrecursionlimit(1000000)

while True:
    S_ = raw_input()
    if S_ == '.':
        break

    lst = []
    for i in range(3):
        for j in range(3):
            for k in range(3):
                lst.append((str(i), str(j), str(k)))
    
    ans = 0
    for p in lst:
        S = S_
        S = S.replace("P", p[0])
        S = S.replace("Q", p[1])
        S = S.replace("R", p[2])
        for loop in range(50):
            for loop2 in range(100):
                S_pre = S
                S = S.replace("-0", "2")
                S = S.replace("-1", "1")
                S = S.replace("-2", "0")
                if S == S_pre:
                    break
            for loop2 in range(50):
                S_pre = S
                S = S.replace("(0*0)", "0")
                S = S.replace("(0*1)", "0")
                S = S.replace("(0*2)", "0")
                S = S.replace("(1*0)", "0")
                S = S.replace("(1*1)", "1")
                S = S.replace("(1*2)", "1")
                S = S.replace("(2*0)", "0")
                S = S.replace("(2*1)", "1")
                S = S.replace("(2*2)", "2")
                S = S.replace("(0+0)", "0")
                S = S.replace("(0+1)", "1")
                S = S.replace("(0+2)", "2")
                S = S.replace("(1+0)", "1")
                S = S.replace("(1+1)", "1")
                S = S.replace("(1+2)", "2")
                S = S.replace("(2+0)", "2")
                S = S.replace("(2+1)", "2")
                S = S.replace("(2+2)", "2")
                if S == S_pre:
                    break
        if S == "2":
            ans += 1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S_ = raw_input()
    if S_ == '.':
        break

    ans = 0
    for p, q, r in it.product([0, 1, 2], repeat = 3):
        S = S_
        S = S.replace("P", str(p)).replace("Q", str(q)).replace("R", str(r))

        while len(S) != 1:
            S = S.replace("-0", "2")
            S = S.replace("-1", "1")
            S = S.replace("-2", "0")
            for a, b in it.product([0, 1, 2], repeat = 2):
                S = S.replace("(%d*%d)" % (a, b), str(min(a, b)))
                S = S.replace("(%d+%d)" % (a, b), str(max(a, b)))
            
        if S == "2":
            ans += 1
    print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product

class thee(int):
    def __add__(self, that):
        return thee(max(int(self), int(that)))

    def __mul__(self, that):
        return thee(min(int(self), int(that)))
    
    def __neg__(self):
        T = [2, 1, 0]
        return thee(T[int(self)])

S = input()
while S != ".":
    for x in list("012PQR"):
        S = S.replace(x, "thee({})".format(x))
    ans = 0
    for P, Q, R in product(range(3), repeat=3):
        ans += 2 == int(eval(S))
    print(ans)
    S = input()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    m = {}
    def f(s):
        k = s
        if k in m:
            return m[k]
        t = set(re.findall(r"\([^()]+\)", s))
        while t:
            for c in t:
                s = s.replace(c, f(c[1:-1]))
            t = set(re.findall(r"\([^()]+\)", s))
        while '-' in s:
            s = s.replace('-1', '1')
            s = s.replace('-2', '0')
            s = s.replace('-0', '2')
        r = s[0]
        for i in range(len(s)//2):
            if s[i*2+1] == '*':
                r = min(r,s[i*2+2])
            else:
                r = max(r,s[i*2+2])
        m[k] = r
        return r

    while True:
        s = S()
        if s == '.':
            break

        tr = 0
        for P,Q,R in itertools.product(['0', '1', '2'], repeat=3):
            ts = s.replace('P', P)
            ts = ts.replace('Q', Q)
            ts = ts.replace('R', R)
            if f(ts) == '2':
                tr += 1

        rr.append(tr)

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
import itertools
s = ""
def satisfy(p, q, r):
	global s
	f = s.replace("P", str(p)).replace("Q", str(q)).replace("R", str(r))
	while len(f) > 1:
		f = f.replace("-0", "2").replace("-1", "1").replace("-2", "0")
		for x, y in itertools.product(xrange(3), repeat=2):
			f = f.replace("(%d*%d)" % (x, y), str(min(x, y)))
			f = f.replace("(%d+%d)" % (x, y), str(max(x, y)))
	return f == "2"
while True:
	s = raw_input()
	if s == ".": break
	count = 0
	for p, q, r in itertools.product(xrange(3), repeat=3):
		if satisfy(p, q, r):
			count += 1
	print count

Submission status: Accepted

Solution code:
import itertools
s = ""
while True:
	s = raw_input()
	if s == ".": break
	count = 0
	for p, q, r in itertools.product(xrange(3), repeat=3):
		f = s.replace("P", str(p)).replace("Q", str(q)).replace("R", str(r))
		while len(f) > 1:
			f = f.replace("-0", "2").replace("-1", "1").replace("-2", "0")
			for x, y in itertools.product(xrange(3), repeat=2):
				f = f.replace("(%d*%d)" % (x, y), str(min(x, y)))
				f = f.replace("(%d+%d)" % (x, y), str(max(x, y)))
		if f == "2":
			count += 1
	print count

Submission status: Accepted

Solution code:
from collections import deque


def AND(a, b):
    if a == "0" or b == "0":
        return "0"
    elif a == b == "2":
        return "2"
    else:
        return "1"


def OR(a, b):
    if a == "2" or b == "2":
        return 2
    elif a == b == "0":
        return "0"
    else:
        return "1"


def NOT(a):
    if a.count("-") % 2 == 1:
        if a[0] == "0":
            return "2"
        elif a[0] == "2":
            return "0"
        else:
            return "1"
    else:
        return a[0]


def solve(S):
    que = deque()
    for s in S:
        if s == ")":
            formula = ""
            while True:
                q = que.pop()
                if q == "(":
                    break
                formula += q
            if "+" in formula:
                a, b = formula.split("+")
                a = NOT(a)
                b = NOT(b)
                que.append(str(OR(a, b)))
            if "*" in formula:
                a, b = formula.split("*")
                a = NOT(a)
                b = NOT(b)
                que.append(str(AND(a, b)))
        else:
            que.append(s)
    return NOT("".join(reversed(que)))


while True:
    S = input()
    if S == ".":
        break
    count = 0
    for p in range(3):
        for q in range(3):
            for r in range(3):
                if solve(S.replace("P", str(p)).replace("Q", str(q)).replace("R", str(r))) == "2":
                    count += 1
    print(count)

Submission status: Accepted

Solution code:
def multi(a, b) :
    if a == 0 :
        return 0
    elif a == 1 :
        if b == 0 :
            return 0
        else :
            return 1
    else :
        return b

def add(a, b) :
    if a == 0 :
        return b
    elif a == 1 :
        if b == 2 :
            return 2
        else :
            return 1
    else :
        return 2

def minus(a) :
    return (2 - a)

def calc(l) : # '('、')'のない計算式
    l = list(l)
    
    #'-'を計算
    i = len(l)-1
    while True :
        if i < 0 :
            break
        if l[i] == '-' :
            print
            l[i] = str(minus(int(l[i+1])))
            del l[i+1]
        i -= 1 
        
    #'*'を計算
    i = 0
    while True :
        if i >= len(l) :
            break
        if l[i] == '*' :
            l[i-1] = str(multi(int(l[i-1]), int(l[i+1])))
            del l[i:i+2]
        else :
            i += 1
    
    #'+'を計算
    i = 0
    while True :
        if i >= len(l) :
            break
        if l[i] == '+' :
            l[i-1] = str(add(int(l[i-1]), int(l[i+1])))
            del l[i:i+2]
        else :
            i += 1
    return ''.join(l)
    

        
            
def main(l) :
    l = list(l)
    while '(' in l :
        for i in range(len(l)) :
            if l[i] == '(' :
                start = i
            elif l[i] == ')' :
                A = ''.join(l[start+1:i])
                del l[start:i+1]
                l.insert(start, calc(A))
                break
    if len(l) != 1 :
        l = calc(l)
    return ''.join(l)

while True :
    input_l = input()
    if input_l == '.' :
        break
    
    cnt = 0
    for p in ['0', '1', '2'] :
        for q in ['0', '1', '2'] :
            for r in ['0', '1', '2'] :
                l = input_l
                if 'P' in l :
                    l = l.replace('P', p)
                if 'Q' in l :
                    l = l.replace('Q', q)
                if 'R' in l :
                    l = l.replace('R', r)
                if main(l) == '2' :
                    cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import re
# and
def and_def(a, b):
    return str(min(int(a), int(b)))

# or
def or_def(a, b):
    return str(max(int(a), int(b)))

# not
def not_def(a):
    return str(2 - int(a))

def match(struct):
    if re.fullmatch(r'\-[0,1,2]', struct):
        return not_def(struct[-1])
    if re.fullmatch(r'[0,1,2]\+[0,1,2]', struct):
        return or_def(struct[0], struct[-1])
    if re.fullmatch(r'[0,1,2]\*[0,1,2]', struct):
        return and_def(struct[0], struct[-1])
    if re.fullmatch(r'[0,1,2]', struct):
        return struct
    if re.fullmatch(r'\([0,1,2]\)', struct):
        return struct[1]
    return struct

def parse(struct):
    tmpstruct = ''
    check, minas = False, False
    if len(struct) == 1:
        return struct

    for i in range(len(struct)):
        if not check:
            if struct[i] == '(':
                check = [')', '(']
                tmp = 1
                num = i
            elif struct[i] == '-':
                check = ['0', '1', '2', '(']
                minas = True
                num = i
            else:
                tmpstruct += struct[i]

        else:
            if struct[i] in check:
                if struct[i] == ')':
                    tmp -= 1
                    if not tmp:
                        if not minas:
                            tmpstruct += parse(struct[num+1: i])
                        else:
                            tmpstruct += not_def(parse(struct[num + 1: i + 1]))
                            minas = False
                        check = False
                elif struct[i] == '(' and check == ['0', '1', '2', '(']:
                    check = [')', '(']
                    tmp = 1
                elif struct[i] == '(':
                    tmp += 1
                else:
                    tmpstruct += not_def(parse(struct[num + 1: i + 1]))
                    check = False
                    minas = False
        tmpstruct = match(tmpstruct)
    return tmpstruct


def change_PQR(string, P, Q, R):
    ret = ''
    for i in string:
        if i == 'P':
            ret += str(P)
        elif i == 'Q':
            ret += str(Q)
        elif i == 'R':
            ret += str(R)
        else:
            ret += i
    return ret


while True:
    struct = input()
    if struct == '.':
        break

    ans = 0
    for i in (0, 1, 2):
        for j in (0, 1, 2):
            for k in (0, 1, 2):
                tmpstr = struct
                if parse(change_PQR(tmpstr, i, j, k)) == '2':
                    ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def parseParenthesis(formula):
    pos = 0
    count = 0
    while True:
        if formula[pos] == '(':
            count += 1
        elif formula[pos] == ')':
            count -= 1
        elif count == 1 and (formula[pos] == '+' or formula[pos] == '*'):
            sign = formula[pos]
            formulaA = formula[1:pos]
            formulaB = formula[pos + 1: -1]
            return formulaA, sign, formulaB
        pos += 1

def eval_or(a, b):
    if a == '0':
        return b
    elif a == '1':
        return '1' if b == '0' else b
    elif a == '2':
        return '2'

def eval_and(a, b):
    if a == '0':
        return '0'
    elif a == '1':
        return '0' if b == '0' else '1'
    elif a == '2':
        return b

def eval_neg(a):
    if a == '1':
        return '1'
    return '2' if a == '0' else '0'

def evaluate(formula, p, q, r):
    if formula == '0' or formula == '1' or formula == '2':
        return formula
    if formula == 'P':
        return p
    if formula == 'Q':
        return q
    if formula == 'R':
        return r

    if formula[0] == '(':
        formulaA, sign, formulaB = parseParenthesis(formula)
        evalA = evaluate(formulaA, p, q, r)
        evalB = evaluate(formulaB, p, q, r)
        if sign == '+':
            return eval_or(evalA, evalB)
        elif sign == '*':
            return eval_and(evalA, evalB)
    elif formula[0] == '-':
        return eval_neg(evaluate(formula[1:], p, q, r))

if __name__ == '__main__':
    while True:
        formula = input().strip()
        if formula == '.':
            break

        count = 0
        for p in range(3):
            for q in range(3):
                for r in range(3):
                    if evaluate(formula, str(p), str(q), str(r)) == '2':
                        count += 1
        print(count)