题解 | #矩阵乘法计算量估算#

矩阵乘法计算量估算

http://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b

把数字四则运算的方法改成矩阵乘法

1.算数：左括号和右括号优先级最低

左括号必须入栈

右括号不入栈，只用于带走左括号

优先级小于等于optr栈顶运算符时，弹出opnd中的两个元素和optr的栈顶做计算，计算结果再压入opnd栈，同时num+=m*n*q

2.矩阵乘法：A m*n B n*q

(AB) m*q，运算次数：m*n*q，连乘时相加

3.操作字符串的处理：寻找字符对应元素的row和col

if(act[i]>='A'&&act[i]<='Z'){matrix p;p.row=ma[act[i]-'A'].row;p.col=ma[act[i]-'A'].col;opnd.push(p);}

4.关于添加乘号：（要细心）字母的后面不是右括号、自己不是尾巴、前面是左括号

if(act[i]>='A'&&act[i]<='Z'&&act[i+1]!=')'&&i!=act.length()-1)
        {
            act.insert(act.begin()+i+1,'*');
        }
        else if((act[i]>='A'&&act[i]<='Z'&&act[i-1]==')')||(act[i]=='('&&act[i-1]==')'))
        {
            act.insert(act.begin()+i,'*');
        }

总代码：

/*矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，
后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。

输入描述：
输入多行，先输入要计算乘法的矩阵个数n，
每个矩阵的行数，列数，总共2n的数，
最后输入要计算的法则:一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，
*/
#include<iostream>
#include<stack>
using namespace std;
typedef struct matrix 
{
	int row;
	int col;
}matrix;
matrix multiply(matrix a,matrix b,char p)
{
	matrix result;
	result.row=a.row;
	result.col=b.col;
	return result;
}
int priority(char c)
{
	switch(c)
	{
		case '(':return 1;break;
		case ')':return 1;break;
		case '*':return 2;break;
        default: return -1;
	}
}
int main()
{
    int n;
    long int num=0;//乘法次数 
    stack<matrix> opnd;
    stack<char> optr;
    matrix ma[15];
    string act;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>ma[i].row>>ma[i].col;
    }
    cin>>act;
    for(int i=0;i<act.length();i++)
    {
    	if(act[i]>='A'&&act[i]<='Z'&&act[i+1]!=')'&&i!=act.length()-1)
    	{
    		act.insert(act.begin()+i+1,'*');
		}
		else if((act[i]>='A'&&act[i]<='Z'&&act[i-1]==')')||(act[i]=='('&&act[i-1]==')'))
		{
			act.insert(act.begin()+i,'*');
		}
	}
//	cout<<act<<endl;
    for(int i=0;i<act.length();i++)
    {
    	if(act[i]>='A'&&act[i]<='Z')
    	{
    		matrix p;
    		p.row=ma[act[i]-'A'].row;
    		p.col=ma[act[i]-'A'].col;
    		opnd.push(p);
		}
		else if(act[i]=='*'||act[i]=='('||act[i]==')')
		{
			if(optr.empty()||priority(act[i])>priority(optr.top())||act[i]=='(')//优先级低或者为左括号 
			optr.push(act[i]);
			else
			{				 
				while(!optr.empty()&&priority(act[i])<=priority(optr.top()))
				{
					if(act[i]==')'&&optr.top()=='(') 
					{
						optr.pop();
						break;
					}
					matrix p=opnd.top();
					opnd.pop();
					matrix q=opnd.top();
					opnd.pop();
					opnd.push(multiply(q,p,optr.top()));
					num+=q.col*q.row*p.col;
					optr.pop();					
				}
				if(act[i]!=')') optr.push(act[i]);
			}
		}
	}
//	while(!opnd.empty())
//	{
//		cout<<opnd.top().row<<" "<<opnd.top().col<<endl;
//		opnd.pop();
//	}
	cout<<num<<endl; 
}