杭电1082Matrix Chain Multiplication

本文主要是介绍杭电1082Matrix Chain Multiplication，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

杭电1082Matrix Chain Multiplication

这道题看oj上评论说很水，可是自己居然想了几个小时，看来对栈的的操作还是不够清晰熟练啊。总体思路就是把先把括号里面的表达式，然后再依次向外消掉括号。我的思路就是把（AB（AA（A）））（A（AB）），先运算成（#（#（#）））（#（#）），然后把这个压入数组中，然后遇到‘）’我们就对数组中的倒数第二个和倒数第三个元素进行判断，代码运行可能会出现（##），若判断的元素为#，则进行两个矩阵的相乘，得到新的矩阵压入到martix栈中，然后消除数组中的匹配的括号和中间的数。这样一次往后，直到栈中的元素只剩下一个，括号匹配完，字符串元素被全部判断。就可以得到总的运算次数。

ps：感觉我的方法不是很巧秒，欢迎大家给出意见
有什么看不懂的也欢迎大家给出意见
AC代码

#include<iostream>
#include<stack>
using namespace std;
struct martix
{int r;//hangint c;//lie
}st[200];
int main()
{int n;cin>>n;char str[10000];char c;// int c1,c2;for(int i=0;i<n;i++){cin>>c;cin>>st[c-'A'].r>>st[c-'A'].c;}while(cin>>str){int flag=0;//stack<char>oz;char oz[10000];int top=0;stack<martix>ys;martix temp;int len=strlen(str);int sum=0;for(int j=0;j<len;j++){if(str[j]=='('){oz[top++]='(';}else if(str[j]<='Z'&&str[j]>='A'){temp=st[str[j]-'A'];j++;while(str[j]<='z'&&str[j]>='A'){if(temp.c==st[str[j]-'A'].r){sum+=temp.c*temp.r*st[str[j]-'A'].c;temp.r=temp.r;temp.c=st[str[j]-'A'].c;j++;                        }else{flag=1;break;}}j--;if(flag){break;}ys.push(temp);oz[top++]='#';}else if(str[j]==')'){martix temp1,temp2;if(ys.size()>1&&top>=3&&(oz[top-3]=='#'||oz[top-2]=='#')){ top-=3;temp2=ys.top();ys.pop();temp1=ys.top();ys.pop();if(temp1.c==temp2.r){sum+=temp1.c*temp1.r*temp2.c;temp.r=temp1.r;temp.c=temp2.c; ys.push(temp);oz[top++]='#';}else{flag=1;break;}}}}if(flag)cout<<"error"<<endl;elsecout<<sum<<endl;           }return 0;
}

这篇关于杭电1082Matrix Chain Multiplication的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！