Sunday, August 17, 2014

uva : 442 - Matrix Chain Multiplication

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
int main()
{
    //freopen("input.txt","r",stdin);
    map<char, int> row;
    map<char, int> coloum;
    stack<char> alphabet;
    stack<int> numrow;
    stack<int> numcoloum;
    int test,i,j,k,l,m,n;
    char ch, a[100000];
    cin >> test;
    while(test--)
    {
        cin>> ch >> m >> n;
        row[ch]=m;
        coloum[ch]=n;
    }
    getchar();
    while(gets(a)!=NULL)
    {
        if(strlen(a)==1)printf("0\n");
        else
        {
            int r1,r2,c1,c2,flag=0,sum=0;
            for(i=0;i<strlen(a);i++)
            {
                if(a[i]>='A'&&a[i]<='Z')
                {
                    ch=a[i];
                    r1=row[ch];
                    c1=coloum[ch];
                    numrow.push(r1);
                    numcoloum.push(c1);
                }
                else if(a[i]==')')
                {
                    r2=numrow.top();
                    c2=numcoloum.top();
                    numrow.pop();
                    numcoloum.pop();
                    r1=numrow.top();
                    c1=numcoloum.top();
                    numrow.pop();
                    numcoloum.pop();
                    if(c1==r2)
                    {
                        sum=sum+r1*c1*c2;
                        numrow.push(r1);
                        numcoloum.push(c2);
                    }
                    else
                    {
                        flag=1;
                        break;

No comments:

Post a Comment