행렬 계산기

응용수학자 짐보 박사는 하루 종일 행렬을 계산한다. 실험실에는 행렬 식을 다루는 뛰어난 프로그램이 있지만, 자원을 너무 많이 써서 휴대용 컴퓨터에서는 쓸 수 없다. 짐보 박사를 위해 행렬 식을 계산하는 작은 프로그램을 작성하라.

식은 아래 BNF로 정의된 간단한 언어로 기술된다(줄바꿈은 NL로 표기). 공백과 줄바꿈도 문법에서 의미를 가진다.

program            ::= assignment | program assignment
assignment         ::= var "=" expr "." NL
var                ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H"
                     | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P"
                     | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X"
                     | "Y" | "Z"
expr               ::= term | expr "+" term | expr "-" term
term               ::= factor | term "*" factor
factor             ::= primary | "-" factor
primary            ::= inum | var | matrix | "(" expr ")"
                     | indexed-primary | transposed-primary
indexed-primary    ::= primary "(" expr "," expr ")"
transposed-primary ::= primary "'"
matrix             ::= "[" row-seq "]"
row-seq            ::= row | row-seq ";" row
row                ::= expr | row " " expr
inum               ::= digit | inum digit
digit              ::= "0" | "1" | "2" | "3" | "4"
                     | "5" | "6" | "7" | "8" | "9"

program은 대입문(assignment)의 나열이다. 각 대입문은 =의 왼쪽에 변수(대문자 A-Z)를, 오른쪽에 행렬 식을 두고 마침표 .와 줄바꿈으로 끝난다. 이는 식의 값을 변수에 대입한다는 뜻이다. 값은 정수 행렬이며, 스칼라 정수와 그 정수 하나만을 원소로 갖는 1x1 행렬은 서로 바꿔 쓸 수 있다.

식(expr)은 하나 이상의 항(term)을 + 또는 -로 이은 것이고, 항은 하나 이상의 인수(factor)를 *로 이은 것이다. 이 이항 연산자들은 왼쪽 결합이다. 인수는 primary이거나 - 뒤에 인수가 오는 형태이며, 이 단항 마이너스는 오른쪽 결합이다. 행렬 A, B에 대해 A+B, A-B, A*B, -A는 통상적인 합, 차, 곱, 부호 반전이다. 덧셈과 뺄셈은 두 행렬의 크기가 같아야 하고, 곱셈은 A의 열 수와 B의 행 수가 같아야 한다.

모든 연산(+, -, *, 단항 -)은 $M = 2^{15} = 32768$을 법으로 계산하므로, 모든 값은 $0$부터 $32767$ 사이의 정수이다. 예를 들어 2-3은 -1이 아니라 32767이다. inum은 $M$보다 작은 음이 아닌 십진 정수이며, var는 같은 변수에 가장 최근에 대입된 행렬을 가리킨다.

matrix는 대괄호 안의 row-seq이다. row-seq는 세미콜론 ;으로 구분된 행(row)의 나열이고, row는 공백 하나로 구분된 식의 나열이다. 예를 들어 [1 2 3;4 5 6]은 행이 1 2 3과 4 5 6인 2x3 행렬이다.

행의 원소 자체가 행렬일 수 있으므로 행렬은 중첩(블록 행렬)될 수 있다. 한 행 안의 원소 행렬들은 행 수가 모두 같아야 하며 가로로 이어 붙고, 이렇게 만들어진 행 블록들은 열 수가 모두 같아야 하며 위에서 아래로 쌓인다. 예를 들어 [[1 2 3;4 5 6] [7 8;9 10] [11;12];13 14 15 16 17 18]은 다음 3x6 행렬이다.

$$\begin{pmatrix} 1&2&3&7&8&11 \ 4&5&6&9&10&12 \ 13&14&15&16&17&18 \end{pmatrix}$$

크기는 일관되어야 한다. [[1 2;3 4] [5;6;7];6 7 8]은 첫 행에서 2x2 행렬과 3x1 행렬이 나란히 놓여 행 수가 달라 유효하지 않고, [1 2;3 4 5]는 두 행의 열 수가 달라 유효하지 않다.

1x1 행렬은 스칼라이므로, 1x1 행렬과 임의의 m x n 행렬의 곱은 항상 정의되며 스칼라배를 뜻한다. 예를 들어 2*[1 2;3 4]와 [1 2;3 4]*3은 모두 행렬의 스칼라배이며, [2]*[1 2;3 4]와 [1 2;3 4]*[3]도 마찬가지이다.

indexed-primary는 primary 뒤에 두 개의 색인 식을 붙인 P(rows,cols) 형태이다. 첫 번째 색인은 1xk 정수 행렬, 두 번째는 1xL 정수 행렬이다. 결과는 (a,b) 원소가 P의 (i_a, j_b) 원소인 kxL 행렬이다. 색인은 1부터 시작하며 같은 값이 여러 번 나올 수 있다. 예를 들어 ([1 2;3 4]+[3 0;0 2])([1],[2])는 2([4 2;3 6]의 (1,2) 원소)이고, [1 2;3 4]([2 1 1],[2 1])은 다음 3x2 행렬이다.

$$\begin{pmatrix} 4&3 \ 2&1 \ 2&1 \end{pmatrix}$$

transposed-primary는 primary 뒤에 작은따옴표 '를 붙인 것으로 전치를 뜻한다. m x n 행렬 A=(a_ij)의 전치는 b_ij = a_ji인 n x m 행렬 B이다. 예를 들어 [1 2;3 4]'는 [1 3;2 4]이다.

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

n
program

여기서 n($1 \le n \le 10$)은 대입문의 개수이고, program은 그 n개의 대입문을 한 줄에 하나씩 위 문법에 따라 적은 것이다. 각 데이터셋의 시작에서 모든 변수는 정의되어 있지 않다.

각 줄의 문자 수는 (줄바꿈을 제외하고) 80을 넘지 않으며, 구문 오류나 의미 오류(예: 정의되지 않은 변수 참조)는 없고, 계산 도중 나타나는 모든 행렬의 행 수와 열 수는 각각 100을 넘지 않는다고 가정해도 된다.

각 데이터셋에 대해, 각 대입문의 식의 값을 순서대로 출력한다. 각 값은 $M$보다 작은 음이 아닌 정수로 출력한다. m x n 행렬이면 m개의 줄을 출력하고, k번째 줄에는 그 행의 원소들을 공백 하나로 구분해 적는다(스칼라는 한 줄에 숫자 하나).

한 데이터셋의 마지막 값을 출력한 뒤에는 마이너스 기호가 정확히 다섯 개인 줄 -----을 출력한다. 그 밖의 문자는 출력하지 않는다.