首页 > 代码库 > UVa442 Matrix Chain Multiplication （栈）
UVa442 Matrix Chain Multiplication （栈）
链接：http://acm.hust.edu.cn/vjudge/problem/19085
分析：用栈来实现一个简单的表达式求值。输入表达式保证合法，比如（A（BC））把BC看成一个整体D那么（A（BC））就是AD，所以这些表达式都是在不断重复嵌套相同的结构A*B。遍历表达式，遇到字母则将对应矩阵压入栈中，遇到右括号则将栈顶两个矩阵弹出，判断是否能进行乘法，如果能则累加乘法次数，再将相乘后的矩阵压栈，如果不能则将error置为true，退出循环。
1 #include <iostream> 2 #include <string> 3 #include <stack> 4 using namespace std; 5 6 struct Matrix { 7 int a, b; 8 Matrix(int a = 0, int b = 0): a(a), b(b) {} 9 } m[26];10 11 stack<Matrix> s;12 13 int main() {14 int n;15 cin >> n;16 for (int i = 0; i < n; i++) {17 string name;18 cin >> name;19 int k = name[0] - ‘A‘;20 cin >> m[k].a >> m[k].b;21 }22 string expr;23 while (cin >> expr) {24 int len = expr.length();25 bool error = false;26 int ans = 0;27 for (int i = 0; i < len; i++) {28 if (isalpha(expr[i])) s.push(m[expr[i] - ‘A‘]);29 else if (expr[i] == ‘)‘) {30 Matrix m2 = s.top(); s.pop();31 Matrix m1 = s.top(); s.pop();32 if(m1.b != m2.a) { error = true; break; }33 ans += m1.a * m1.b * m2.b;34 s.push(Matrix(m1.a, m2.b));35 }36 }37 if (error) cout << "error" << endl; else cout << ans << endl;38 }39 return 0;40 }
UVa442 Matrix Chain Multiplication （栈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。