cho.sh

삼항 연산자

아직 제출이 없습니다시간 제한0.5초메모리 제한1024 MB

문제

NN개의 참/거짓 변수를 가진 식이 주어진다. 변수의 값으로 가능한 2N2^N개의 경우에 대하여 식의 값이 00인 경우의 수를 구하는 프로그램을 작성하여라.

이 문제에서 식은 아래 BNF 표기법에서 expression\text{expression}을 뜻한다.

  • boolean::=‘0’ | ‘1’\text{boolean} ::= \text{‘0’ | ‘1’}
  • \text{variable} ::= \text{‘a’ | ‘b’ | ... | N번째 알파벳 소문자}
  • value::=boolean | variable\text{value} ::= \text{boolean | variable}
  • condition::=value ‘==’ value\text{condition} ::= \text{value ‘==’ value}
  • expression::=value | condition ‘?’ expression ‘:’ expression \text{expression} ::= \text{value | condition ‘?’ expression ‘:’ expression }

식의 값은 eval(expression)eval(\text{expression})을 의미하며 아래와 같이 재귀적으로 계산된다. 잘 생각해보면 올바른 식이 주어졌을 때 해당 식을 계산하는 방법이 유일하다는 것을 알 수 있다.

  • eval(value)=valueeval(\text{value}) = \text{value}
  • eval(condition)=eval(value1 ‘==’ value2)={1if eval(value1)=eval(value2)\ 0otherwise eval(\text{condition}) = eval(\text{value1 ‘==’ value2}) = \begin{cases} 1 & \text{if } eval(\text{value1}) = eval(\text{value2}) \\\ 0 & \text{otherwise} \end{cases}
  • eval(expression)=eval(value)=valueeval(\text{expression}) = eval(\text{value}) = \text{value}
  • eval(expression)=eval(condition ‘?’ expression1 ‘:’ expression2) ={ eval(expression1)if eval(condition)=1\ eval(expression2)otherwise eval(\text{expression}) = eval(\text{condition ‘?’ expression1 ‘:’ expression2}) \\\ = \begin{cases} eval(\text{expression1}) & \text{if } eval(\text{condition}) = 1 \\\ eval(\text{expression2}) & \text{otherwise} \end{cases}

입력

첫 번째 줄에는 변수의 수 NN (1≤N≤261 \le N \le 26)이 주어진다.

두 번째 줄에는 식에 해당하는 길이 11 이상 1 0001\ 000 이하의 문자열이 주어진다. 식은 ‘0’, ‘1’, ‘a’-(N번째 알파벳 소문자), ‘=’, ‘?’, ‘:’로만 구성되며 올바른 식만 주어진다.

출력

식의 값이 00이 되도록 변수의 값을 할당하는 방법의 수를 출력한다.