矩阵连乘求乘法次数（java实现）

　　【矩阵连乘求乘法次数问题】
　　题目：输入n个矩阵（矩阵名称为大写英文字母表示）的维度和一些矩阵链乘表达式，输出乘法的次数，也就是计算量。如果乘法无法进行，输出error。假定A是mn矩阵，B是np矩阵，那么A乘B是mp矩阵，乘法次数为mnp，一般我们把乘法次数称之为本次计算的计算量。如果A的列数不等于B的行数，则乘法无法进行。
　　例如：A是5010的，B是1020的，C是205的，则（A（BC））的乘法次数为10205（BC的乘法次数）50105（（A（BC））的乘法次数）3500。两次乘法的计算量之和。
　　【输入形式】
　　矩阵个数n。
　　下面n行分别为n个矩阵的名称、行数和列数。
　　需要计算的矩阵连乘的表达式。
　　【输出形式】
　　给出表达式的计算量（为n1次乘法的计算量之和）
　　【样例输入】
　　3hrA105
　　B56
　　C67
　　（A（BC））
　　【样例输出】
　　560hr解题思路：本题需要根据矩阵的表达式来规定计算的顺序，需要通过栈的数据结构来解决计算的先后问题，可以从表达式的左括号和右括号寻找突破点，例如读到一个左括号就向栈里放入一个矩阵，读到一个右括号就计算一个矩阵得出新的矩阵并记录乘法次数，重复上述步骤，直到栈空为止，得出最终的结果。
　　【详细分析】：
　　首先需声明变量以及定义栈。
　　intMatrixlengthin。nextInt（）；矩阵个数
　　int〔〕Matrixnewint〔Matrixlength2〕；
　　Matrixlength为矩阵的个数，数组Matrix用于存放矩阵的行列值。
　　int〔〕stack1newint〔s。length（）〕；行值
　　int〔〕stack2newint〔s。length（）〕；列值
　　inttop0；栈指针
　　intj0；用于遍历Matrix
　　inttimes0；
　　其中，stack1用于存放矩阵的行值，stack2用于存放矩阵的列值，两个栈共用一个栈指针top，j用于遍历数组Matrix。偶数（j2）位用于存储行值，奇数位（j21）用于存储列值。
　　本例中Matrix〔〕｛10，5，5，6，6，7｝
　　staticfinalStringSABCDEFGHIJKLMNOPQRSTUVWXYZ；
　　定义矩阵字母表
　　for（inti0；iMatrixlength；i）｛输入矩阵行列值
　　b〔i〕in。next（）。charAt（0）；
　　Matrix〔i2〕in。nextInt（）；
　　Matrix〔i21〕in。nextInt（）；
　　｝
　　Stringsin。next（）；输入矩阵连乘表达式
　　输入矩阵和矩阵表达式：A105B56C67（A（BC））
　　for（inti0；iMatrix。length21；i）｛判断矩阵是否符合连乘条件
　　if（Matrix〔i21〕！Matrix〔（i1）2〕）｛
　　return0；
　　｝
　　｝
　　进行矩阵连乘之前需要判断这些矩阵是否符合连乘条件，即判断相邻矩阵的列值和行值是否相等。
　　核心语句：
　　for（inti0；is。length（）；i）｛入栈
　　if（s。charAt（i）（）｛
　　if（s。charAt（i1）！（）｛找到最内层左括号时矩阵入栈
　　stack1〔top〕Matrix〔j2〕；
　　stack2〔top〕Matrix〔j21〕；
　　j；
　　top；
　　｝
　　｝
　　elseif（S。indexOf（s。charAt（i））！1s。charAt（i1）））｛字母左边为右括号需提前top
　　top；
　　｝
　　elseif（s。charAt（i）））｛出栈
　　if（j2Matrix。lengths。charAt（i1）！））｛遇到第一个右括号时矩阵入栈
　　stack1〔top〕Matrix〔j2〕；
　　stack2〔top〕Matrix〔j21〕；
　　j；
　　｝
　　timesstack1〔top〕stack2〔top〕stack1〔top1〕；
　　stack2〔top1〕stack2〔top〕；相乘后所得新矩阵的列值
　　top；
　　if（top0j2Matrix。length）｛栈空但矩阵未完成遍历
　　top；
　　｝
　　｝
　　｝
　　returntimes；
　　｝
　　从左向右依次扫描表达式s的字符，读到最内层的左括号（右边为矩阵字母）时读入一个矩阵，将其放入栈中，top，读到第一个右括号（右括号左边为矩阵字母）时，放入一个矩阵并计算times值，并得到新的矩阵的行列值，其行列值将上一个矩阵的行列值覆盖，top1。elseif（S。indexOf（s。charAt（i））！1s。charAt（i1）））｛字母左边为右括号需提前top
　　top；
　　｝
　　不过也有特殊的情况，如（A（（BC）D）），在读到最后一个右括号时，需读入D矩阵，而在读入矩阵C后，top1，得到新的矩阵时top还指在新的矩阵，这时需要我们提前top来防止读入的矩阵D将新的矩阵行列值覆盖。
　　【举例分析】：A105、B56、C67，（A（BC））
　　【完整代码】：
　　publicclassSolution｛
　　staticfinalStringSABCDEFGHIJKLMN；
　　publicstaticintsolution（Strings，int〔〕Matrix）｛
　　int〔〕stack1newint〔s。length（）〕；行值
　　int〔〕stack2newint〔s。length（）〕；列值
　　inttop0；栈指针
　　intj0；用于遍历Matrix
　　inttimes0；
　　for（inti0；iMatrix。length21；i）｛判断矩阵是否符合连乘条件
　　if（Matrix〔i21〕！Matrix〔（i1）2〕）｛
　　return0；
　　｝
　　｝
　　for（inti0；is。length（）；i）｛入栈
　　if（s。charAt（i）（）｛
　　if（s。charAt（i1）！（）｛找到最内层左括号时矩阵入栈
　　stack1〔top〕Matrix〔j2〕；
　　stack2〔top〕Matrix〔j21〕；
　　j；
　　top；
　　｝
　　｝
　　elseif（S。indexOf（s。charAt（i））！1s。charAt（i1）））｛字母左边为右括号需提前top
　　top；
　　｝
　　elseif（s。charAt（i）））｛出栈
　　if（j2Matrix。lengths。charAt（i1）！））｛遇到第一个右括号时矩阵入栈
　　stack1〔top〕Matrix〔j2〕；
　　stack2〔top〕Matrix〔j21〕；
　　j；
　　｝
　　timesstack1〔top〕stack2〔top〕stack1〔top1〕；
　　stack2〔top1〕stack2〔top〕；相乘后所得新矩阵的列值
　　top；
　　if（top0j2Matrix。length）｛栈空但矩阵未完成遍历
　　top；
　　｝
　　｝
　　｝
　　returntimes；
　　｝
　　测试类：
　　publicstaticvoidmain（String〔〕args）｛
　　ScannerinnewScanner（System。in）；
　　intMatrixlengthin。nextInt（）；矩阵个数
　　int〔〕Matrixnewint〔Matrixlength2〕；
　　char〔〕bnewchar〔Matrixlength〕；矩阵大写字母，对计算无用
　　for（inti0；iMatrixlength；i）｛输入矩阵行列值
　　b〔i〕in。next（）。charAt（0）；
　　Matrix〔i2〕in。nextInt（）；
　　Matrix〔i21〕in。nextInt（）；
　　｝
　　Stringsin。next（）；输入矩阵连乘表达式
　　if（solution（s，Matrix）0）｛不符合连乘条件
　　System。out。println（error）；
　　｝else｛
　　System。out。println（solution（s，Matrix））；
　　｝
　　｝
　　｝
　　样例输出：
　　你们学会了吗？