ASCII 수식 | cho.sh

문제

오래된 논문이나 기술 문서에 실린 수식은 타자기로 여러 줄에 걸쳐 인쇄되곤 했다. 이때 숫자, 기호, 공백을 찍기 위해서는 고정폭(monospace) 글꼴이 필요하다. 다음 수식을 살펴보자.

$$\left( 1 - \frac{4}{3^2}\right)^2 \times -5 + 6$$

이 수식은 다음과 같이 네 줄로 인쇄된다.

        4   2
( 1 - ---- )  * - 5 + 6
        2
       3

여기서 - 5는 단항 마이너스 뒤에 5가 오는 것을 뜻한다. 이렇게 여러 줄로 표현된 식을 ASCII 수식이라고 부른다.

당신의 임무는 이러한 ASCII 수식(예: 오래된 논문을 OCR로 인식해 얻은 것)의 구조를 인식하고 그 값을 계산하는 프로그램을 작성하는 것이다.

문제를 단순화하기 위해, ASCII 수식은 다음 규칙으로만 만들어진다고 가정한다. 문법은 표 H.1과 같다.

표 H.1: ASCII 수식을 구성하는 규칙(배커스-나우어 형식과 유사). 각 상자는 하나의 종단/비종단 기호에 대응하는 문자들의 직사각형 영역(셀)을 나타낸다. 문법적으로 필요한 공백 문자는 여기서 마침표 .로 명시적으로 표시하였다.

  (I)     expr ::= term | expr.+.term | expr.-.term
 (II)     term ::= factor | term.*.factor
(III)   factor ::= powexpr | fraction | -.factor
                                    digit
 (IV)  powexpr ::= primary | primary
  (V)  primary ::= digit | (.expr.)
                      expr
 (VI) fraction ::= ---------
                      expr
(VII)    digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

그림 H.1: 위쪽 선(top-line), 기준선(base-line), 아래쪽 선(bottom-line). 셀 예시 — expr $1-\frac{4}{3^2}$, fraction $\frac{4}{3^2}$, powexpr $3^2$, digit $3$.

종단 기호는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, (, ), 그리고 공백 문자다.
비종단 기호는 expr, term, factor, powexpr, primary, fraction, digit이며 시작 기호는 expr이다.
셀은 하나의 종단/비종단 기호에 대응하는 문자들의 직사각형 영역이다(그림 H.1). 셀 안에는 공백만으로 이루어진 불필요한 행이나 열이 없다. 종단 기호에 대응하는 셀은 문자 하나로 이루어진다. 비종단 기호에 대응하는 셀은 그 자손에 대응하는 셀(들)을 포함하되, 서로 부분적으로 겹치지 않는다.
각 셀에는 기준선, 위쪽 선, 아래쪽 선이 있다. 규칙 I, II, III, V의 우변에 있는 자식 셀들의 기준선은 서로 정렬된다. 그 세로 위치가 좌변 셀의 기준선 위치를 정한다.
powexpr는 하나의 primary와 선택적인 digit로 이루어진다. 이 digit는 primary 셀의 기준선보다 한 줄 위에 놓이며, 서로 가로로 맞붙어 있다. powexpr의 기준선은 primary의 기준선과 같다.
fraction은 분수선(vinculum)이라 부르는 3개 이상의 연속된 하이픈으로 나타낸다. 피제수(분자) expr는 분수선 바로 위에, 제수(분모) expr는 바로 아래에 놓인다. 분수선의 하이픈 개수 $w_h$는 $w_h = 2 + \max(w_1, w_2)$이며, 여기서 $w_1$, $w_2$는 각각 분자 셀과 분모 셀의 너비다. 두 셀은 가운데 정렬되어, 왼쪽에 $\lceil (w_h - w_k)/2 \rceil$개, 오른쪽에 $\lfloor (w_h - w_k)/2 \rfloor$개의 공백 문자가 놓인다($k = 1, 2$). fraction의 기준선은 분수선의 위치다.
digit는 문자 하나로 이루어진다.

예를 들어, 음의 분수 $-\frac{3}{4}$는 세 줄로 표현된다.

   3
- ---
   4

여기서 가장 왼쪽의 하이픈은 단항 마이너스 연산자를 뜻한다. 단항 마이너스와 분수선 사이에는 공백 하나가 필요하다.

분수 $\frac{3+4 \times -2}{-1-2^2}$는 네 줄로 표현된다.

 3 + 4 * - 2
-------------
          2
   - 1 - 2

여기서 분자 셀과 분모 셀의 너비는 각각 11과 8이다. 따라서 분수선의 하이픈 개수는 $2 + \max(11, 8) = 13$이다. 분모는 왼쪽에 $\lceil (13 - 8)/2 \rceil = 3$개, 오른쪽에 $\lfloor (13 - 8)/2 \rfloor = 2$개의 공백으로 가운데 정렬된다.

powexpr $\left(4^2\right)^3$는 두 줄로 표현된다.

   2  3
( 4  )

여기서 2에 해당하는 셀은 4에 해당하는 셀의 기준선보다 한 줄 위에 놓이고, 3에 해당하는 셀은 primary $\left(4^2\right)$에 해당하는 셀의 기준선보다 한 줄 위에 놓인다.

입력

입력은 여러 개의 데이터셋으로 이루어지며, 마지막에 0만 있는 줄이 온다. 각 데이터셋의 형식은 다음과 같다.

n
str1
str2
.
.
.
strn

$n$은 양의 정수로, 하나의 ASCII 수식 셀을 나타내는, 길이가 모두 같은 다음 $n$개의 줄의 개수를 뜻한다. $str_k$는 그 셀의 $k$번째 줄이며, 각 공백 문자는 마침표로 바뀌어 있다.

$n \le 20$이고 각 줄의 길이는 80 이하라고 가정해도 된다.

출력

각 데이터셋에 대해, 2011 미만의 음이 아닌 정수 하나를 한 줄에 출력한다. 이 정수는 법(modulo) 2011에서의 ASCII 수식의 값이다. 그 밖의 문자는 출력하면 안 된다.

분모가 0이거나 2011의 배수인 분수는 없다.

powexpr $x^0$은 1로 정의하며, $x^y$($y$는 양의 정수)는 $x$를 $y$번 곱한 값 $x \times x \times \cdots \times x$로 정의한다.

분수 $\frac{x}{y}$는 법 2011에서 $x$와 $y$의 역원의 곱, 즉 $x \times \mathrm{inv}(y)$로 계산한다. 2011은 소수이므로, $y$($1 \le y < 2011$)의 역원은 $z \times y \equiv 1 \pmod{2011}$을 만족하는 정수 $z$($1 \le z < 2011$)로 유일하게 정해진다.