//题目刚做是思路出现了问题,栈中元素只需要row 和column 即可。
//字典可以包含一个char,但更好的做法是将char型转换成下标
//新函数append()
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
using namespace std;
struct Type
{
int row;
int column;
Type():row(0),column(0){}
Type(int a,int b):row(a),column(b){}
};
bool operator!=(const Type &a,const Type &b)//要定义成const型,否则编译出错
{
return (a.column!=b.column || a.row!=b.row);//这里曾经出错,!=
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
Type p[30];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
char ch;
int a,b;
cin>>ch>>a>>b;
p[ch-'A'].row=a;
p[ch-'A'].column=b;
}
string line;
while(cin>>line)
{
int num=0;
stack<Type> s;
line.insert(0,"(");//这里插入元素为字符串型
line.append(")");
int flag=1;
for(int i=0;i<line.size() && flag==1;i++)
{
if(line[i]=='(')
{
s.push(Type(-1,0));
}
else if(line[i]==')')
{
Type t1,t2;
if(!s.empty() && s.top()!=Type(-1,0))
{
t2=s.top();
s.pop();
}
while(!s.empty() && s.top()!=Type(-1,0))
{
t1=s.top();
if(t1.column!=t2.row)
{
printf("error\n");
flag=0;
break;
}
else
{
s.pop();
num+=t1.row*t1.column*t2.column;
t2.row=t1.row;
}
}
s.pop();
s.push(t2);
}
else
{
s.push(p[line[i]-'A']);
}
}
if(flag==1)
printf("%d\n",num);
}
return 0;
}
分享到:
相关推荐
矩阵链乘法 该程序找到了最有效的乘法矩阵的方法。 该程序实现的复杂度为O(n ^ 3),并用O(n)括住最终输出 输入规范:第一行包含n,下一行包含a0,...,an,以空格分隔。 假定所有数字都是正数且适合int且n最多为...
Matrix Chain Multiplication is perhaps the quintessential example of dynamic programming. The problem can be stated as follows: given a chain <A1, A2,..., An> of n matrices, where for i = 1, 2,....
题目描述: 输入n个矩阵的维度和一些矩阵链乘表达式,输出乘法的次数。如果乘法无法进行,输出error。假定A是m*n矩阵,B是n*p矩阵,那么AB是m*p矩阵,乘法次数为m*n*p。如果A的列数和B的行数不同,则乘法无法进行。...
struct Matrix { int a, b; Matrix(int a = 0,int b=0):a(a),b(b){} }m[26]; stack s; int main() { int n; cin >> n; for (int i = 0; i > name; int k = name[0] - 'A'; cin >> m[k].a >> m[k].b; } ...
矩阵链乘法 计算与'n'个矩阵相乘所需的最小标量乘法数,并确定必须相乘的顺序 实现递归,动态编程和算法的简化版本,以解决矩阵链乘法。 比较所有三种算法的运行时间,以了解这些方法之间的区别。...
Matrix chain multiplication in c
讲解经典算法,并且有例题讲解。书中部分内容:2.2 动态规划 (Dynamic Programming) 2.2.1 背包问题... 2.3.5 Matrix-chain multiplication 2.3.6 树上的独立集 (Max Independent set in tree) 等,不一一列出
15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...
15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...
15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...
15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...
3Matrices: addition and multiplication . . . . . . . . . . . . . . .4 4The transpose of a matrix . . . . . . . . . . . . . . . . . . . . .6 5Square matrices . . . . . . . . . . . . . . . . . . . . . ....
15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...
l5.2 Matrix-chain multiplication 331 l5.3 Elements of dynamic programming 339 15.4 Longest common subsequence 350 l5.5 Optimal binary search trees 356 l6 Greedy Algorithms 370 l6.l An activity-...
Fig10_46.cpp: Dynamic programming algorithm for optimal chain matrix multiplication, with a test program Fig10_53.cpp: All-pairs algorithm, with a test program Random.h: Header file for random ...
100天编码挑战编码很有趣,每天编码每天编写代码,通过发出拉取请求将解决方案添加到仓库中,还可以编辑/添加多个解决方案来解决已解决的问题从今天开始编码! 您编写的代码越多,增长的就越多每个人都应该学习编程...
1094 Matrix Chain Multiplication 简单题 1536 Labyrinth 简单题 1100 Mondriaan s Dream 简单题,DP可以过,不过据说有复杂的组合公式 1103 Hike on a Graph 简单题 1134 Strategic Game 简单题 1147 ...
1094 Matrix Chain Multiplication 简单题 1536 Labyrinth 简单题 1100 Mondriaan s Dream 简单题,DP可以过,不过据说有复杂的组合公式 1103 Hike on a Graph 简单题 1134 Strategic Game 简单题 1147 ...
3 Matrices: addition and multiplication . . . . . . . . . . . . . . . 4 4 The transpose of a matrix . . . . . . . . . . . . . . . . . . . . . 6 5 Square matrices . . . . . . . . . . . . . . . . . . . ...