ZOJ 1094 Matrix Chain Multiplication

ZOJ 1094 Matrix Chain Multiplication

矩阵链乘的时候,不同的结合方式所需要的运算次数不同,肯定存在一个乘法次数最少的结合方式(可以用dp求出),此题以此为背景,给出结合方式,求出所需要的乘法次数.算是经典的栈的应用,维护两个栈,KUO是括号的栈,M表示矩阵栈,从每一个表达式的开始,遇到左括号和矩阵就压入相应的栈，遇到右括号就进行栈顶两个元素的运算，直到最后。如果某两个元素不能相乘，输出error

#include<iostream>
#include<string>
#include<cstring>
#include<stack>

using namespace std;
struct MATRIX
{
    int hang,lie;
}m[26],t,A,B;
int main(void)
{
    char c;
    int N,i,TotalCount,error;
    string ss;
    stack<char> KUO;
    stack<MATRIX> M;//两个栈

    cin >> N;
    for( i = 0; i < N; i++ )
    {
        cin >> c;
        cin >> m[c-'A'].hang >> m[c-'A'].lie;
    }
    while( cin >> ss )
    {
        TotalCount = error = 0;
        for( i = 0; i < ss.length(); i++ )
        {
            if( ss[i] == '(' )//左括号压入
                KUO.push('(');
            else if( isalpha( ss[i] ) )//矩阵压入
                M.push( m[ ss[i]-'A' ] );
            else
            {
                KUO.pop();
                B = M.top();M.pop();
                A = M.top();M.pop();
                if( A.lie != B.hang )
                    {error = 1;break;}
                TotalCount += A.hang*A.lie*B.lie;
                t.hang = A.hang;
                t.lie  = B.lie;
                M.push(t);
            }
        }
        while( !KUO.empty() ) KUO.pop();
        while( !M.empty() ) M.pop();//两个栈清空

        if( error ) cout << "error\n";
        else cout << TotalCount << endl;
    }
    return 0;
}