当前位置:编程学习 > C/C++ >>

zoj - 1094 - Matrix Chain Multiplication

题意:输入不超过26个矩阵的行数和列数,接着来一些表达式询问,求各条表达式需要多少次基本运算。

 ——>>用STL开2个栈,一个用来存“(”,一个用来存储矩阵,扫描表达式,当碰到矩阵时,放入矩阵栈;当碰到“(”时,放入符号栈;当碰到“)”的时候,从矩阵栈中取(退)2个矩阵相乘并记录乘法次数和,并将相乘后的矩阵放入矩阵栈,从符号栈中删除1个“(”,最后输出结果即可。

[cpp] 
#include <iostream> 
#include <stack> 
 
using namespace std; 
 
struct Matrix     //矩阵类型,包括行数和列数 

    int row;        //行数 
    int col;        //列数 
}; 
 
int main() 

    int n, i;       //n为输入的矩阵个数 
    Matrix mat[30];     //用来存储各个单矩阵(最多只有26个,所以开30的空间有了!!!) 
    char c; 
    cin>>n; 
    for(i = 0; i < n; i++) 
    { 
        cin>>c; 
        int index = (int)(c-'A');       //让矩阵数组的下标0,1,2...就标志着A,B,C... 
        cin>>mat[index].row>>mat[index].col;      //存入对应的行数和列数 
    } 
 
    string s;       //以字符串的形式输入每行测试数据 
    while(cin>>s) 
    { 
        long long sum = 0;      //基本乘法数之和,初始为0 
        int len = s.length(); 
        stack<char> st_sign;        //该栈用来存储"(" 
        stack<Matrix> st_node;        //该栈用来存储"矩阵" 
        int ok = 1;     //ok用来标志是否出现error的现象 
        for(i = 0; i < len; i++)        //扫描各个字符 
            if(s[i] == ')')     //当出现")"时,必有"("与其对应 
            { 
                int right_value = st_node.top().col;      //从栈中取出矩阵数据,右矩阵的列数 
                int mid_value_right = st_node.top().row;      //右矩阵的行数 
                st_node.pop(); 
                int left_value = st_node.top().row;       //从栈中取出矩阵数据,左矩阵的行数 
                int mid_value_left = st_node.top().col;     //左矩阵的列数 
                if(mid_value_left != mid_value_right)       //当 左矩阵的列数 != 右矩阵的行数 时 
                { 
                    ok = 0; 
                    break; 
                } 
                st_node.pop(); 
                st_sign.pop(); 
                sum += left_value * mid_value_left * right_value;       //累加基本乘法次数 
                Matrix newmat; 
                newmat.row = left_value; 
                newmat.col = right_value; 
                st_node.push(newmat);      //新建一个矩阵,行数为左矩阵的行数,列数为右矩阵的列数,进栈 
            } 
            else if(s[i] == '(')        //碰到"("直接放入符号栈即可 
                st_sign.push('('); 
            else        //当扫到字母即矩阵的时候 
            { 
                int new_index = (int)(s[i]-'A');        //转换下标 
                st_node.push(mat[new_index]);       //将该矩阵放入矩阵栈 
            } 
        if(ok) 
            cout<<sum<<endl; 
        else 
            cout<<"error"<<endl; 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,