Contents

1. 1. 题目：
2. 2. 测试用例：
3. 3. 分析：

题目：

　　输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数，如果乘法无法进行，输出
error。假定A是mn矩阵，B是np矩阵，那么AB是mp矩阵，乘法次数为mn*p。如果A的
列数不等于B的行数，则乘法无法进行。

测试用例：

3
A 50 10
B 10 20
C 20 5
(A(BC))
3500

//10205(BC的乘法次数) + 50105(A(BC)的乘法次数) = 3500

分析：

　　遇到字母入栈，遇到右括号时出栈并计算，然后将计算结果入栈。因为输入保证合法，括号无需入栈。

　　简单的表达式解析可以借助栈来完成

#include <iostream>
#include <stack>
#include <string>
#include <cstdio>
using namespace std;

struct Matrix{
    int a, b;
    //Maxtrix(int a = 0, int b = 0): a(a), b(b) {}  //构造函数
}m[26];//26个英文字母

stack<Matrix> s;

int main(){

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        string name;
        cin >> name;
        int k = name[0] - 'A';
        cin >> m[k].a >> m[k].b;           //将原数据，矩阵的行列记录下来
    }
    string expr;
    while(cin >> expr)
    {
        bool error = false;
        int len = expr.length();
        int ans = 0;                       //记录乘法次数
        for(int i = 0; i < len; i++){
            if(isalpha(expr[i]))
                s.push(m[expr[i] - 'A']);  //把相应的矩阵的数据推入栈
            else if(expr[i] == ')')
            {
                Matrix m2 = s.top();
                s.pop();
                Matrix m1 = s.top();
                s.pop();
                if(m1.b != m2.a){
                    error = true;
                    break;
                }
                ans += m1.a * m1.b * m2.b;
                //s.push(Matrix(m1.a, m2.b));
                Matrix m3;
                m3.a = m1.a;
                m3.b = m2.b;
                s.push(m3);
            }
        }
    	if(error)
            printf("error\n");
    	else
            printf("%d\n", ans);
    }
    return 0;
}