POJ (2246) Matrix Chain Multiplication

spoiler posted @ 2011年4月08日 15:56 in Ecole Polytechnique Contest 解题报告 , 1182 阅读

题目分析:简单的后缀表达式,把每个表达式存放在string 变量里,然后从前到后遍历一边,当遇到'('直接存放在记录运算符的栈里,如果是 字母就把这个字母对应的 节点存放在,记录运算节点的栈里!最后当遇到 ')' 如果记录运算符号的栈里为空,就说明 括号不对称!所以得出error!否则把栈里的'('的出栈!然后把记录运算节点的栈里取出两个运算节点!对这两个节点进行判断,是否满足矩阵运算规则,如果不满足,判错!满足的话记录下他们的乘积!并且 将两个节点合并成一个节点 存放回 在记录运算节点的栈里!

算法详细过程 就是这样 下面是我的代码 如有改正的地方请您留言 谢谢

#include<iostream>
#include<stdio.h>
#include<stack>
#include<cstring>
using namespace std;

struct node{
	int x,y;
}s[30];
int n;
void input(){
	char c;
	while(n--){
		cin>>c;
		int t=c-'A';
		cin>>s[t].x>>s[t].y;
	}
}

int cal(string str){
	int i,k=str.length(),ans=0;
	struct node a,b;
	stack<char>sn;
	stack<struct node>st;
	for(i=0;i<k;i++){
		if(str[i]=='(')
			sn.push(str[i]);	
		else if(str[i]>='A'&&str[i]<='Z')
			st.push(s[str[i]-'A']);
		else{
			if(sn.empty())
				return -1;
			sn.pop();
			b=st.top();
			st.pop();
			a=st.top();
			st.pop();
			if(a.y!=b.x)
				return -1;
			ans+=a.x*b.x*b.y;
			a.y=b.y;
			st.push(a);
			
		}
			
	}
	return ans;
}

int main(){
	int sum;
	string str;
	cin>>n;
	input();
	while(cin>>str){
		sum=cal(str);
		if(sum==-1)
			printf("error\n");
		else
			printf("%d\n",sum);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter