Sunday, 19 August 2012

UVa 442 - Matrix Chain Multiplication Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define MX 12
#define MOD 1000000007

struct Z{
    int row,col;
    char c;
};

main()
{
    int n,r,c;
    Z z,z1,z2;
    int pos1,pos2;
    string s;
    cin>>n;
    vector<Z>mat;
    stack<Z>mat2;
    //stack<Z>mat;
    while(n--)
    {
        cin>>z.c>>z.row>>z.col;
        mat.PB(z);
        mat2.push(z);
    }
    int matl=mat.size();
    while(cin>>s)
    {
        bool chk=true;
        int sl=s.length();
        stack<Z>stk;
        stk=mat2;
        LL sum=0;
        FOR(i,sl)
        {
            if(s[i]==')')
            {
                Z aa,bb;
                aa=stk.top();
                stk.pop();
                bb=stk.top();
                stk.pop();

                if(bb.col==aa.row)
                {

                    sum+=(bb.row*bb.col*aa.col);
                    z.c='x';
                    z.row=bb.row;
                    z.col=aa.col;
                    stk.push(z);
                }
                else
                {
                    chk=false;
                    break;
                }
            }

            else if(isalpha(s[i]))
            {
                FOR(j,matl)
                    if(mat[j].c==s[i])
                    {
                        z.c=mat[j].c;
                        z.row=mat[j].row;
                        //cout<<z.row<<endl;
                        z.col=mat[j].col;
                        //cout<<z.col<<endl;
                        stk.push(z);
                        break;
                    }
            }
        }
    if(chk)
        cout<<sum<<endl;
    else
        cout<<"error"<<endl;
    }
return 0;
}

2 comments: