삼항 연산자 2 timer 1s memory 1024MB

삼항 연산자는

(condition) ? (value_if_true) : (value_if_false)

와 같이 생긴 연산자로, condition이 참일 경우 value_if_true로 평가되고 아닐 경우 value_if_false로 평가된다.

또한, 삼항 연산자 안에 또 삼항 연산자를 쓸 수 있다. 다시 말해 condition과 value에도 삼항 연산자가 들어갈 수 있다.

만약, 삼항 연산자로만 이루어진 표현식에서 괄호를 뺀다면 표현식을 여러 방법으로 해석할 수 있다. 예를 들어 b?i:n?g:o 는

((b)?(i):(n)) ? (g) : (o)   또는   (b) ? (i) : ((n)?(g):(o))

로 해석할 수 있다.

괄호가 없는 삼항 연산자로만 구성된 표현식이 주어지면 해당 식을 몇 가지 방법으로 해석할 수 있는지 구하는 프로그램을 작성하여라.

구체적으로 정의하자면,

<expr> ::= (<expr>)?(<expr>):(<expr>) | <variable>
<variable> ::= a | b | c | ... | z

위의 BNF(Backus–Naur form)에서 <expr>로 나타낼 수 있는 문자열 중에서 괄호를 제거하고 비교하였을 때 입력받은 표현식과 같은 문자열이 되는 경우의 수를 구해야 한다.

경우의 수가 너무 클 수 있으므로, 이 수를 소수인 1\, 000\, 000\, 007(=10^9+7)로 나눈 나머지를 계산하여라.