LRJ入门经典（基础篇）——3.矩阵链乘

3.矩阵链乘

问题描述：
输入n个矩阵的维度和一些矩阵链乘表达式,输出乘法的次数.如果无法进行,输出error.如果A是m*n矩阵,B是n*p的矩阵,乘法次数为m*n*p如果A的列数不等于B的行数,则乘法无法进行.
思路：
栈的简单应用。定义矩阵结构体;输入矩阵;输入运算公式;遇到字母进栈;遇到‘）’出栈顶两元素;如果无法计算则输出error;如果可以计算则将计算结果入栈更新乘法次数

#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
using namespace std;

struct Matrix {//定义矩阵结构体
    int a, b;
} m[26];

//矩阵栈
stack<Matrix> s;

int main(){
    //输入矩阵信息
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        string name;
        cin>>name;
        //将矩阵名字映射成数字
        int k = name[0] - 'A';
        cin >> m[k].a >> m[k].b;
    }

    //输入运算公式
    string expr;
    while(cin >> expr){
        int length = expr.length();
        int ans = 0;
        bool state = true;

        for(int i=0;i<length;i++){
            if(isalpha(expr[i])) s.push(m[expr[i]-'A']);
            if(expr[i]==')'){
                //栈顶两元素出栈计算
                Matrix m2 = s.top();
                s.pop();
                Matrix m1 = s.top();
                s.pop();
                //无法计算
                if(m1.b != m2.a){
                    state = true;
                    break;
                }else{//可以计算
                    Matrix m;
                    m.a = m1.a;
                    m.b = m2.b;
                    //计算结果入站
                    s.push(m);
                    //更新乘法次数
                    ans += m1.a*m1.b*m2.b;
                    state = false;
                }
            }

        }

        if(state)
            cout<< "error" <<endl;
        else
            cout<< ans <<endl;
    }
    return 0;
}

测试数据

2
A
2  2
B
2  3
(AB)
12