UVa442 Matrix Chain Multiplication[模拟][栈]

题目链接:https://vjudge.net/problem/UVA-442

用stack库来模拟栈的操作

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

struct Matrix{
	int a,b;
	Matrix(int a=0,int b=0):
		a(a),b(b){}
};

int n;
Matrix m[26];
stack<Matrix> s;

int main(){
//	freopen("temp.in","r",stdin);
	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 len=expr.length();
		bool error=false;
		int ans=0;
		for(int i=0;i<len;i++){
			if(isalpha(expr[i]))  s.push(m[expr[i]-'A']);
			else  if(expr[i]==')'){
				Matrix m2=s.top();  s.pop();
				Matrix m1=s.top();  s.pop();
				if(m1.b!=m2.a){
					error=true;
					break;
				}
				ans+=m1.a*m1.b*m2.b;
				s.push(Matrix(m1.a,m2.b));
			}
		}
		if(error)  puts("error");
		else  cout<<ans<<endl;
	}
	return 0;
} 

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s

%d 博主赞过: