UVa 442 Matrix Chain Multiplication

　　用栈进行模拟，读取字符串，然后逐个字符进行判断，是‘（’就忽略，是大写字母的话入栈，是‘）’的话就弹出两个矩阵判断计算。

　　代码如下：

Code 1

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <cstring>
 4 #include <stack>
 5 using namespace std;
 6 
 7 struct Matrix
 8 {
 9     int row, col;
10 };
11 
12 stack<Matrix> st;
13 
14 int main()
15 {
16 #ifdef LOCAL
17     freopen("in", "r", stdin);
18 #endif
19     int n;
20     int matrix[26][2];
21     while(scanf("%d", &n) != EOF && n)
22     {
23         memset(matrix, 0, sizeof(matrix));
24         while(n--)
25         {
26             char s[5];
27             scanf("%s",s);
28             int p = s[0] - 'A';
29             scanf("%d%d", &matrix[p][0], &matrix[p][1]);
30         }
31         char s[10000];
32         while(scanf("%s", s) != EOF)
33         {
34             while(!st.empty()) st.pop();
35             int ans = 0, error = 0;
36             int len = strlen(s);
37             for(int i = 0; i < len; i++)
38             {
39                 if(s[i] == '(')   continue;
40                 else if(isupper(s[i]))  
41                 {
42                     Matrix t;
43                     t.row = matrix[s[i]-'A'][0];
44                     t.col = matrix[s[i]-'A'][1];
45                     st.push(t);
46                 }
47                 else if(s[i] == ')')
48                 {
49                     Matrix b = st.top();
50                     st.pop();
51                     Matrix a = st.top();
52                     st.pop();
53                     if(a.col == b.row)
54                     {
55                         ans += a.row * a.col * b.col;
56                         Matrix t;
57                         t.row = a.row;
58                         t.col = b.col;
59                         st.push(t);
60                     }
61                     else
62                     {
63                         error = 1; 
64                         break;
65                     }
66                 }
67             }
68             if(error)   printf("error\n");
69             else printf("%d\n", ans);
70         }
71     }
72     return 0;
73 }

　　忘了原来曾经做过这道题，今天又做了一遍，写完提交后才发现已经写过了，UVa对做过的题只给一个浅绿色的标志，是在考验我的眼力吗...，不说了，必须贴一下代码，要不就对不起我辛辛苦苦才敲出来的代码啊

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cctype>
 4 #include <stack>
 5 #define MAXN 1000
 6 using namespace std;
 7 
 8 struct Matrix
 9 {
10     int r;
11     int c;
12 } mat[26];
13 
14 int main()
15 {
16 #ifdef LOCAL
17     freopen("in", "r", stdin);
18 #endif
19     int n;
20     scanf("%d", &n);
21     for (int i = 0; i < n; i++)
22     {
23         char s[10];
24         scanf("%s", s);
25         int ix = s[0] - 'A';
26         scanf("%d%d", &mat[ix].r, &mat[ix].c);
27     }
28     char s[MAXN];
29     while (scanf("%s", s) != EOF)
30     {
31         stack<Matrix> st;
32         int res = 0;
33         bool error = false;
34         int len = strlen(s);
35         for (int i = 0; i < len; i++)
36         {
37             if (s[i] == '(')   continue;
38             else if (isupper(s[i]))
39             {
40                 int ix = s[i] - 'A';
41                 Matrix t = (Matrix){mat[ix].r, mat[ix].c};
42                 st.push(t);
43             }
44             else if (s[i] == ')')
45             {
46                 Matrix b = st.top();
47                 st.pop();
48                 Matrix a = st.top();
49                 st.pop();
50                 if (a.c != b.r)
51                 {
52                     error = true;
53                     break;
54                 }
55                 else
56                 {
57                     res += a.r * a.c * b.c;
58                     Matrix t = (Matrix){a.r, b.c};
59                     st.push(t);
60                 }
61             }
62         }
63         if (error)   printf("error\n");
64         else printf("%d\n", res);
65     }
66     return 0;
67 }

Code 2

　　不过也算是有点收获吧，复习了一下结构体，同时又被Matrix a = st.pop();坑了一把...然后就是，第一个代码只用了8ms，而这个却用了22ms，差到哪里去了呢？感觉也差多少啊　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　-- 2013.7.8