假设您必须计算一个表达式,如ABCDE,其中A、B、C、D和E是矩阵。 由于矩阵乘法是关联的,所以执行乘法的顺序是任意的。 然而,所需的初等乘法的数量很大程度上取决于求值顺序 您可以选择。 例如,设A为5010矩阵,B为1020矩阵,C为205矩阵。有两个 计算ABC的不同策略,即(AB)C和A(B*C)。 第一个需要15000次基本乘法,但第二个只需要3500次。 你的工作是编写一个程序,确定所需的初等乘法的数量 对于给定的评估策略。
输入 输入由两部分组成:矩阵列表和表达式列表。 输入文件的第一行包含一个整数n(1≤n≤26),表示 第一部分中的矩阵。接下来的n行各包含一个大写字母,指定 矩阵和两个整数,指定矩阵的行数和列数。 输入文件的第二部分严格遵循以下语法(在EBNF中给出): SecondPart=行{行}<EOF> 直线=表达式 表达式=矩阵|“(“表达式表达式”)” 矩阵=“A”|“B”|“C”|…|“X”|“Y”|“Z” 输出 对于输入文件第二部分中的每个表达式,打印一行包含单词“error” 如果表达式的求值由于不匹配矩阵而导致错误。否则打印一个 包含计算表达式所需的基本乘法次数的行 由括号指定。
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
思路
读入矩阵,用一个结构体数组储存矩阵,其中成员x为行,y为列。读入矩阵表达式,遇到右括号时让两个元素a和b出栈,如果a的列不等于b的行,矩阵不可乘,输出error;若矩阵可乘,将a和b按矩阵乘法规则相乘得到矩阵c,将c入栈,需要进行乘法运算的总数sum加上本次矩阵乘法需要进行乘法运算的次数,最后输出sum。
AC代码
#include <iostream>
#include <stack>
#include <sstream>
#define AUTHOR "HEX9CF"
using namespace std;
#define MAXN 100005;
int n;
struct S
{
int x;
int y;
} m[30];
stack<S> s;
S x(S a, S b)
{
return S{a.x, b.y};
}
int xx(S a, S b)
{
return a.x * a.y * b.y;
}
int getIndex(char ch)
{
return ch - 'A';
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
char ch;
int t;
cin >> ch;
t = getIndex(ch);
cin >> m[t].x >> m[t].y;
// cout << t;
}
string str;
while (cin >> str)
{
char ch;
int sum = 0;
bool err = false;
stringstream ss(str);
// cout << str << endl;
while (ss >> ch)
{
// read line
// cout << ch << endl;
if (ch >= 'A' && ch <= 'Z')
{
int t;
t = getIndex(ch);
s.push(m[t]);
}
else if (')' == ch)
{
S a, b, c;
b = s.top();
s.pop();
a = s.top();
s.pop();
if (a.y != b.x)
{
err = true;
break;
}
c = x(a, b);
sum += xx(a, b);
s.push(c);
}
}
if (err)
{
cout << "error" << endl;
}
else
{
cout << sum << endl;
}
}
return 0;
}
标签:ch,20,Matrix,Chain,int,题解,矩阵,表达式,乘法
From: https://blog.51cto.com/HEX9CF/7703865