442. Умножение матриц

Для того чтобы перемножить две матрицы с размерами m * n и n * p, требуется выполнить m * n * p умножений. В задаче необходимо вычислить количество операций умножения для заданной последовательности перемножения матриц.

Вход. Первая строка содержит количество перемножаемых матриц n (1 £ n £ 26). Каждая из следующих n строк содержит имя матрицы (заглавная латинская буква) и ее размеры. Следующая часть входных данных содержит матричные выражения, описываемые грамматикой:

SecondPart = Line { Line } <EOF>

Line = Expression <CR>

Expression = Matrix | "(" Expression Expression ")"

Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

Выход. Для каждого входного выражения вывести количество умножений, необходимых для его вычисления.

Пример входа

9

A 50 10

B 10 20

C 20 5

D 30 35

E 35 15

F 15 5

G 5 10

H 10 20

I 20 25

A

B

C

(AA)

(AB)

(AC)

(A(BC))

((AB)C)

(((((DE)F)G)H)I)

(D(E(F(G(HI)))))

((D(EF))((GH)I))

Пример выхода

0

0

0

error

10000

error

3500

15000

40500

47500

15125

РЕШЕНИЕ

синтаксический анализ

Анализ алгоритма

Следует реализовать синтаксический разбор и интерпретацию строки, содержащую матричное выражение.

Реализация алгоритма

Переменная Error будет установлена в 1, если входное выражение или синтаксически неверно, или содержит в своем вычислении произведение несовместимых матриц. Две матрицы a * b и c * d несовместимы по умножению, если b ¹ c. Массив символов s содержит строку с матричным выражением. Элементы dim[i][0] и dim[i][1] содержат размеры матрицы с именем ‘A’ + i. Стек st используется при интерпретации входного выражения и содержит размеры матриц как пары чисел.

int Error, dim[26][2];

char s[1000];

stack<pair<int,int> > st;

В процедурах expression и matrix реализуется интерпретация входного выражения. В процедуре matrix заносятся в стек размеры текущей распознаваемой матрицы.

void matrix(void)

{

st.push(make_pair(dim[s[ptr] - 'A'][0],dim[s[ptr] - 'A'][1]));

ptr++;

}

Процедура expression реализует правило

Expression = Matrix | "(" Expression Expression ")"

Если распозначаемый символ является открывающей скобкой, то реализуется вторая часть правила. Иначе символ считается именем матрицы и вызывается процедура matrix. Если значение Error равно 1, то следует завершить работу процедуры.

void expression(void)

{

pair<int,int> a,b;

if (Error) return;

if (s[ptr] == '(')

{

ptr++;

expression(); if (Error) return;

expression(); if (Error) return;

После второго вызова процедуры expression на вершине стека располагаются размеры двух матриц, которые перемножаются. Заносим их в переменные a и b. Для перемножения матриц с размерами (a.first, a.second) и (b.first, b.second) следует выполнить a.first * a.second * b.second операций умножений, в результате получается матрица с размерами (a.first, b.second).

b = st.top();st.pop();

a = st.top();st.pop();

if (a.second != b.first) {Error = 1; return;}

res += a.first * a.second * b.second;

st.push(make_pair(a.first,b.second));

После распознания двух выражений должна следовать закрывающаяся скобка. Если ее нет, то установить Error = 1.

if (s[ptr] != ')') {Error = 1; return;}

ptr++;

} else matrix();

}

Основная часть программы. Читаем количество матриц n и их имена и размеры. Заносим размеры матриц в массив dim.

scanf("%d\n",&n);

for(i = 0; i < n; i++)

{

scanf("%c %d %d\n",&name,&x,&y);

dim[name - 'A'][0] = x; dim[name - 'A'][1] = y;

}

Входные выражения читаем в массив s. Вызываем процедуру интерпретации expression. Переменная ptr является указателем на текущий символ в строке s.

while(gets(s))

{

Error = res = ptr = 0;expression();

Чистим содержание стека st для его использования при интерпретации следующего выражения.

while(!st.empty()) st.pop();

В зависимости от значения переменной Error выводим результат. Переменная res содержит количество выполненых умножений.

if (Error) printf("error\n");

else printf("%d\n",res);

}