矩阵链乘（Matrix Chain Multiplication

[题目链接]

思路

核心问题是正确处理多个括号内矩阵的运算顺序，使用stack将矩阵存入，每当遇见字符 ' ) ' 时对栈顶的两个元素进行操作，便可以正确处理顺序。另使用结构体保存矩阵的行列值。

备注

1.题目出入输出较长，在测试阶段重复输入数据较繁琐，因此使用：

#define LOCAL
#ifdef LOCAL 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif

详见：竞赛输入与输出
2.在输入阶段，栈的取出阶段使用输出进行测试，找出问题。例，在取栈后对取出的元素进行输出，发现了取栈顺序错误的问题。

代码

#include<iostream>
#include<stack>
#include<string>
//#include<cctype>      头文件<string>包含了isalpha函数，这里可以不引用<cctype>
#define LOCAL
using namespace std;

struct matrix     
{                       //建立结构体数组，存放矩阵A~Z的行、列
    int line,column;
    matrix(int line=0,int column=0):line(line),column(column){}   //结构体初始化操作
}mar[26];

stack<matrix> s;        //使用栈存放待计算数组

void main()
{
    #ifdef LOCAL        //文件输入与输出
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    while(n--)          //录入矩阵
    {
        string c;
        cin>>c;
        int k=c[0]-'A'; //将矩阵A储存在数组下标为0的空间内，以此类推
        cin>>mar[k].line>>mar[k].column;
    }
    //cout<<mar[0].line<<mar[0].column<<mar[1].line<<mar[1].column<<endl; 测试
    string str;
    while(cin>>str)
    {
        int len=str.length();
        int ans=0;  
        bool error=false;
        for(int i=0;i<len;i++)
        {
            if(isalpha(str[i]))
                s.push(mar[str[i]-'A']);
            else if(str[i]==')')
            {
                matrix m2=s.top();s.pop();
                matrix m1=s.top();s.pop();
                //cout<<m1.line<<m1.column<<m2.line<<m2.column<<endl; 测试
                if(m1.column==m2.line)
                {
                    ans+=m1.line*m1.column*m2.column;
                    s.push(matrix(m1.line,m2.column));
                }
                else
                {
                    error=true;
                    break;
                }
            }
        }
        if(error)
            cout<<"error"<<endl;
        else
            cout<<ans<<endl;
    }
}