算法竞赛入门经典（第二版-刘汝佳） Uva442 经验总结

算法竞赛入门经典（第二版-刘汝佳） Uva442 经验总结"/>

算法竞赛入门经典（第二版-刘汝佳） Uva442 经验总结

题目链接

Sample Input
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

Sample Output
0
0
0
error
10000
error
3500
15000
40500
47500
15125

一开始的思路是用链表存放每个矩阵的行、列、字母，然后把字母入栈，根据字母来找对应的矩阵，程序写出来后虽然能过样例，但是却无法AC，而且代码又长，时间并不是很宽裕就放弃原先的思路去学习刘汝佳老师的代码

自己写的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
typedef struct multi* mt;
struct multi
{int m;int n;char c;mt next;multi() : next(NULL) {}
};
stack<char> pt;
char order;
int sum = 0, flag = 0, n, nl;
mt head = new struct multi(), p1 = NULL;mt find(char c) {//根据字母来查找对应的矩阵p1 = head;while (p1 != NULL) {if (p1->c == c) {return p1;}p1 = p1->next;}
}void Insert(mt temp) { //新乘出来的矩阵插入链表末尾p1 = head;while (p1->next != NULL) {p1 = p1->next;}p1->next = temp;
}void Clear() {  //有关数据全部初始化sum = 0;order = 'a'; // 给新的矩阵赋予字母编号，便于查找while (!pt.empty()) {pt.pop();}int j = 0;p1 = head->next;while (j < nl - 1) {p1 = p1->next;j++;}if (p1 != NULL)p1->next = NULL;
}/*void test() {cout << "---------------" << endl;p1 = head->next;while (p1 != NULL) {cout << p1->c << " " << p1->m << " " << p1->n << endl;p1 = p1->next;}cout << "----------------" << endl;
}*/int main() {//freopen("D://in.txt", "r", stdin);ios::sync_with_stdio(0); p1 = head;cin >> n;nl = n;while (n--) {mt p2 = new struct multi();cin >> p2->c >> p2->m >> p2->n;p1->next = p2;p1 = p2;}getchar();string cmd;while (getline(cin, cmd)) {if (cmd.length() == 1) {cout << "0" << endl;continue;}else {Clear();//test();for (int i = 0; i < cmd.length(); i++) {if (cmd[i] == '(' || (cmd[i] <= 'Z' && cmd[i] >= 'A')) {pt.push(cmd[i]);}else {char c = pt.top(); pt.pop();char c2 = pt.top(); pt.pop();mt tmp = find(c), tmp2 = find(c2);if (tmp2->n != tmp->m) {cout << "error" << endl;flag = 1;break;}else {sum += (tmp2->m) * (tmp2->n) * (tmp->n);mt temp = new struct multi();temp->m = tmp2->m;temp->n = tmp->n;order += 1;temp->c = order;pt.pop();pt.push(order);Insert(temp);}}}if (!flag) {cout << sum << endl;}flag = 0;}}return 0;
}

写完后再看自己的代码是很粗糙的，比如给新的矩阵赋予新的字母，如果给出的表达式过长使得ASCll码超过了255该怎么办，还有每次给新的矩阵开辟新的空间插入链表中，计算下一个表达式的时候这些空间没有释放，还存留着，造成内存泄漏，是个很不好的习惯，而刘汝佳老师的代码很精简，比我的要好多了。。。

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
struct multi
{int m;int n;multi(int a = 0, int b = 0) :m(a), n(b){}
} t[26];
stack<multi> p;int main() {//freopen("D://in.txt", "r", stdin);int n;cin >> n;for (int i = 0; i < n; i++) {char c;cin >> c;cin >> t[c - 'A'].m >> t[c - 'A'].n;}string expr;while (cin >> expr) {bool error = false;int ans = 0;for (int i = 0; i < expr.length(); i++) {if (isalpha(expr[i])) {p.push(t[expr[i] - 'A']);}else if (expr[i] == ')') {multi t2 = p.top(); p.pop();multi t1 = p.top(); p.pop();if (t1.n != t2.m) {error = true;break;}else {ans += t1.m * t1.n * t2.n;p.push(multi(t1.m, t2.n));//直接创建一个multi结构体并入栈，这里第一次看过}}}if (error) {cout << "error\n";}else {cout << ans << endl;}}return 0;
}