Калькулятор матриц
Доктор Джимбо, прикладной математик, целый день занимается вычислением матриц для своих исследований. В своей лаборатории он использует мощное программное обеспечение для работы с матрицами, но не может использовать его вне лаборатории из-за высокой нагрузки на ресурсы. Поэтому он хочет иметь небольшую программу для работы с матрицами на своем ноутбуке.
Ваша задача — создать программу, которая будет вычислять матричные выражения. Эти выражения описываются на простом языке, синтаксис которого представлен в Таблице 1. Обратите внимание, что пробелы и новые строки играют важную роль в синтаксисе.
Таблица 1: Синтаксис в BNF (новая строка обозначена как NL)
Начальный символ этого синтаксиса — программа, которая представляет собой последовательность присваиваний, как указано в Таблице 1. Каждое присваивание имеет переменную слева от знака равенства ("=") и матричное выражение справа, за которым следует точка и новая строка (NL). Это означает присваивание значения выражения переменной. Переменная (var в Таблице 1) обозначается заглавной римской буквой. Значение выражения (expr) — это матрица или скаляр, элементы которого являются целыми числами. Здесь скалярное целое число и 1×1 матрица, единственный элемент которой — это то же самое целое число, могут использоваться взаимозаменяемо.
Выражение — это один или несколько членов, соединенных символами "+" или "-". Член — это один или несколько множителей, соединенных символом "*". Эти операторы ("+", "-", "*") являются левоассоциативными.
Множитель — это либо первичное выражение (primary), либо символ "-" перед множителем. Этот унарный оператор "-" является правоассоциативным.
Значение операторов такое же, как и в обычной арифметике на матрицах: Обозначая матрицы как A и B, A+B, A−B, A∗B и −A определяются как сумма, разность, произведение и отрицание матриц. Размеры A и B должны быть одинаковыми для сложения и вычитания. Количество столбцов A и количество строк B должны быть одинаковыми для умножения.
Обратите внимание, что все операторы +, −, ∗ и унарный − представляют собой вычисления сложения, вычитания, умножения и отрицания по модулю M = 215 = 32768, соответственно. Таким образом, все значения являются неотрицательными целыми числами от 0 до 32767 включительно. Например, результат выражения 2−3 должен быть 32767, а не −1.
inum — это неотрицательное десятичное целое число меньше M.
var представляет матрицу, которая присваивается переменной var в последнем предшествующем операторе присваивания той же переменной.
matrix представляет собой математическую матрицу, аналогичную двумерному массиву, элементы которого являются целыми числами. Она обозначается row-seq с парой заключающих квадратных скобок. row-seq представляет собой последовательность строк, две соседние из которых разделены точкой с запятой. row представляет собой последовательность выражений, две соседние из которых разделены пробелом.
Например, [1 2 3;4 5 6] представляет матрицу . Первая строка имеет три целых числа, разделенных двумя пробелами, т.е. "1 2 3". Вторая строка имеет три целых числа, т.е. "4 5 6". Здесь row-seq состоит из двух строк, разделенных точкой с запятой. Матрица обозначается row-seq с парой квадратных скобок.
Обратите внимание, что элементы строки могут быть снова матрицами. Таким образом, может появиться вложенное представление матрицы. Количество строк значения каждого выражения строки должно быть одинаковым, а количество столбцов значения каждой строки row-seq должно быть одинаковым.
Например, матрица, представленная
[[1 2 3;4 5 6] [7 8;9 10] [11;12];13 14 15 16 17 18]
является . Размеры матриц должны быть согласованы, как упоминалось выше, чтобы сформировать корректную матрицу в качестве результата. Например, [[1 2;3 4] [5;6;7];6 7 8] не согласован, так как первая строка "[1 2;3 4] [5;6;7]" имеет две матрицы (2×2 и 3×1), количество строк которых различно. [1 2;3 4 5] не согласован, так как количество столбцов двух строк различно.
Умножение 1×1 матрицы и m×n матрицы определено для произвольных m > 0 и n > 0, так как 1×1 матрицы могут рассматриваться как скалярное целое число. Например, 2*[1 2;3 4] и [1 2;3 4]*3 представляют произведения скаляра и матрицы 2 ∗ и . [2]*[1 2;3 4] и [1 2;3 4]*[3] также определены аналогично.
Индексированное первичное выражение — это первичное выражение, за которым следуют два выражения в качестве индексов. Первый индекс — это 1×k целочисленная матрица, обозначенная как (i_1 i_2 ... i_k), а второй индекс — это 1×l целочисленная матрица, обозначенная как (j_1 j_2 ... j_l). Два индекса указывают на подматрицу, извлеченную из матрицы, которая является значением предшествующего первичного выражения. Размер подматрицы — k×l, и ее (a, b)-элемент является (i_a, j_b)-элементом значения предшествующего первичного выражения. Способ индексирования — с единицы, т.е. первый элемент индексируется как 1.
Например, значение ([1 2;3 4]+[3 0;0 2])([1],[2]) равно 2, так как значение его первичного выражения — это матрица [4 2;3 6], и первый индекс [1] и второй [2] указывают на (1, 2)-элемент матрицы. То же самое целое число может появляться дважды или более в индексной матрице, например, первая индексная матрица выражения [1 2;3 4]([2 1 1],[2 1]) — это [2 1 1], которая имеет две 1. Ее значение — .
Транспонированное первичное выражение — это первичное выражение, за которым следует символ одинарной кавычки ("’"), который указывает на операцию транспонирования. Транспонированная матрица m × n матрицы A = (aij) (i =1, ..., m и j = 1, ..., n) — это n×m матрица B = (bij) (i = 1, . . . , n и j = 1, . . .,m), где bij = aji. Например, значение [1 2;3 4]’ — это .
Входные данные
Входные данные состоят из нескольких наборов данных, за которыми следует строка, содержащая ноль. Каждый набор данных имеет следующий формат.
nprogram
n — это положительное целое число, за которым следует программа, представляющая собой последовательность одиночных или множественных строк, каждая из которых является оператором присваивания, синтаксис которого определен в Таблице 1. n указывает количество операторов присваивания в программе. Все значения vars неопределены в начале программы.
Вы можете предположить следующее:
1 ≤ n ≤ 10,
количество символов в строке не превышает 80 (исключая новую строку),
нет синтаксических ошибок и семантических ошибок (например, ссылка на неопределенную var),
количество строк матриц, появляющихся в вычислениях, не превышает 100, и
количество столбцов матриц, появляющихся в вычислениях, не превышает 100.
Выходные данные
Для каждого набора данных значение выражения каждого оператора присваивания программы должно быть выведено в том же порядке. Все значения должны быть выведены как неотрицательные целые числа меньше M.
Когда значение является m × n матрицей A = (aij) (i = 1, ..., m и j = 1, ..., n), должно быть выведено m строк. В k-й строке (1 ≤ k ≤ m) должны быть выведены целые числа k-й строки, т.е. ak1, . . . , akn, разделенные пробелом.
После вывода последнего значения набора данных должна быть выведена строка, содержащая пять минусов '—–' для удобства чтения.
Вывод не должен содержать никаких других дополнительных символов.