欢迎访问我的Uva题解目录哦 https://blog.****.net/ri*qi/article/details/81149109

题目描述

题意解析

输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。如果乘法无法进行，输出error。
假定A是$m×n$m×n矩阵，B是$p×q$p×q矩阵，当且仅当$n=p$n=p时，可以进行矩阵乘法运算，其乘法次数为$m×n×q$m×n×q

算法设计

本题的表达式比较简单，可以用一个栈来完成：遇到字母时入栈，遇到右括号时出栈并计算，然后结果入栈。因为输入保证合法，括号无须入栈。

C++代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b;
    scanf("%d%*c",&n);//%*c用来吸收换行符
    map<char,pair<int,int>>matrix;//存储矩阵及其行列维度
    for(int i=0;i<n;++i){
        char c;
        scanf("%c%d%d%*c",&c,&a,&b);
        matrix[c]={a,b};
    }
    string line;
    while(getline(cin,line)){
        int ans=0;//乘法次数
        stack<pair<int,int>>s;//栈，元素表示行列维度
        for(char c:line){//遍历一行字符串
            if(c==')'){//遇到右括号
                auto t2=s.top();//存储栈顶元素
                s.pop();//矩阵出栈
                auto t1=s.top();//存储栈顶元素
                s.pop();//矩阵出栈
                if(t1.second!=t2.first){//不能进行乘法运算
                    puts("error");//输出error
                    goto loop;//跳出循环
                }
                ans+=t1.first*t1.second*t2.second;//更新乘法次数
                s.push({t1.first,t2.second});//将乘积矩阵入栈
            }else if(c!='(')//左括号不入栈
                s.push(matrix[c]);
        }
        printf("%d\n",ans);//输出
        loop:;
    }
    return 0;
}