hdu_1082 Matrix Chain Multiplication （字符串）

http://acm.hdu.edu.cn/showproblem.php?pid=1082

分析：

虽然矩阵连乘是动态规划的经典题型，但是这道题却只是对字符串的处理——括号运算的处理。所以利用栈来处理。

当遇到矩阵时入栈，遇到“）” 弹出连个矩阵进行运算，并将运算结果压栈。另者在矩阵相乘时注意两个矩阵是否满足相乘条件。

代码：

#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <ctype.h>
using namespace std;
#define M 30

string s;
int n,ans;
struct node
{
    char c;
    int  row,cal;
}a[M];

bool judge(node x,node y)
{
    return x.row==y.cal;
}

int _find(char c)
{
    for(int i=0;i<n;i++) if(a[i].c==c) return i;
}

void calc()
{
    int len=s.length();
    if(len==1)   {printf("0\n"); return;}

    stack<node> sta;
    ans=0;
    for(int i=0;i<len;i++){
        if(isupper(s[i])){
           int index=_find(s[i]);
           sta.push(a[index]);
        }
        else if(s[i]==‘)‘){
            node x=sta.top(); sta.pop();
            node y=sta.top(); sta.pop();
            if(!judge(x,y))   {printf("error\n");return;}
            node t;
            t.row=y.row; t.cal=x.cal;
            ans+= y.row*y.cal*x.cal;
            sta.push(t);
        }
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;i++) {getchar();scanf("%c%d%d",&a[i].c,&a[i].row,&a[i].cal);}
    while(cin>>s) calc();
    return 0;
}

hdu_1082 Matrix Chain Multiplication （字符串）

原文：http://blog.csdn.net/vuorange/article/details/18405727