문제
In an infinite binary tree: 무한한 크기의 이진트리에서 각노드는 반드시 두개의 자식노드(왼쪽 자식, 오른쪽 자식)를 가진다.
어떤 한 노드의 번호를 X라고 한다면 왼쪽 자식노드의 번호는 2·X 이다.
그리고 오른쪽 자식노드의 번호는 2·X+1이다. 루트 노드의 번호는 1이다.
루트를 시작으로 이진 트리를 순회할 때 각 단계에서 왼쪽 노드부터 가고 오른쪽 노드를 방문한 후에 잠시 멈춘다.
각 순회에서 'L', 'R' , 'P'를 다음과 같이 정의한다.
'L' : 왼쪽 노드로 이동한다.
'R' : 오른쪽 노드로 이동한다.
'P' : 잠시 멈춘다.
순회의 값은 노드의 마지막에 도달했을 때 의 노드의 번호이다.
예를 들자면 RPP순회의 값이 3이라면 LR순회의 값은 5가 된다.
순회의 집합은 문자 'L', 'R', 'P', '*‘로 표시한다. '*'는 패턴상에서 'L'이거나 'R'이거나 'P'로 대치될 수 있다.
예를 들자면 집합 L*R은 LLR이거나 LRR이거나 LPR이 될 수 있다.
집합 **은 LL, LR, LP, RL, RR, RP, PL, PR , PP 될 수 있다.
결론적으로 모든 순회집합의 값은 집합에서 나올 수 있는 모든 순회값들의 총합이다.
주어진 순회집합의 값을 계산하는 프로그램을 작성하라.
입력
순회집합의 값들은 문자열로서 'L', 'R', 'P', '*' 로만 구성되며 길이는 10,000 을 넘지 않는다.
[제약조건]
데이터의 30%는 '*'포함되지 않는다.
데이터의 50%는 '*'의 개수가 3개를 넘지 않는다.
출력
순회집합의 값을 출력하시오.
예제1
P*P
6