1 #include <cstdio>
2 #include <iostream>
3 #include <string>
4 #include <stack>
5
6 using namespace std;
7
8 struct Matrix {
9 int r,c;
10 Matrix(int a = 0, int b = 0) : r(a), c(b) {};
11 }m[26];
12
13 stack<Matrix> s;
14
15 int main()
16 {
17
18 int n;
19 cin >> n;
20 for (int i = 0; i < n; i++) {
21 string name;
22 cin >> name;
23 int k = name[0] - 'A';
24 cin >> m[k].r >> m[k].c;
25
26 }
27
28 string expr;
29 while (cin >> expr) {
30
31 int len = expr.size(); // 獲取字符串的大小,因?yàn)檫@整個(gè)字符串都沒(méi)有空格
32 bool error = false;
33 int ans = 0;
34 for (int i = 0; i < len; i++) { // 循環(huán)整個(gè)表達(dá)式、思路是遇到右括號(hào)就出棧兩個(gè)Matrix進(jìn)行計(jì)算,算完在壓回。
35 // 其實(shí)你可以發(fā)現(xiàn)帶括號(hào)的表達(dá)式十分符合棧,而不僅僅是該題目,首先左括號(hào)越深
36 // 其計(jì)算的有先級(jí)別越高,而右括號(hào)又和左括號(hào)配對(duì),如果我們從左到右讀取一個(gè)表達(dá)式
37 // 每次一遇到右括號(hào),其前面到左括號(hào)的部分肯定就是這個(gè)表達(dá)式最優(yōu)先的部分。
38 if (isalpha(expr[i])) { s.push(m[expr[i] - 'A']); }
39 else if (')' == expr[i]) {
40 Matrix m2 = s.top(); s.pop();
41 Matrix m1 = s.top(); s.pop();
42 if (m1.c != m2.r) { error = true; break; }
43 ans += m1.r * m1.c * m2.c;
44 s.push(Matrix(m1.r, m2.c));
45 }
46
47 }
48
49 if (error) printf("error\n"); else printf("%d\n", ans);
50
51 }
52
53 return 0;
54 }
55
2015/4/10下午6:32:37
By sixleaves