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

Solution (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)

Solution (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)

Solution (Python):



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)

Solution (Python):
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

Solution (Python):
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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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()

        
        
        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 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 = add(expr_value, right)
            elif op == 'MINUS':
                
                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 = mult(term_value, self.factor())
            else:
                raise SyntaxError('Should not arrive here ' + op)

        return term_value

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

        '''

        
        if self._accept('NUM'):
            expr_value = int(self.current_token.value)
        
        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()










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)

Solution (Python):
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))



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

Solution (Python):
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))

Solution (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

Solution (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

Solution (Python):

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()

Solution (Python):
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())

Solution (Python):
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

Solution (Python):
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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import re

def and_def(a, b):
    return str(min(int(a), int(b)))


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


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)

Solution (Python):
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)