用栈，每次遇到右括号就把从左括号到右括号之间的部分全部计算。要在读取字符串的时候左边加一个左括号，右边加一个右括号（一开始没有这么做依然AC了，数据太弱了）。
以下是我的代码：
#include<iostream>
#include<string>
#include<stack>
#include<cstdio>
using namespace std;
const int kMaxn(27);
struct Type
{
Type():a(0),b(0) {}
Type(int aa,int bb):a(aa),b(bb) {}
int a,b;
};
bool operator!=(const Type &a,const Type &b)
{
return (a.a!=b.a || a.b!=b.b);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int n;
cin>>n;
Type r[kMaxn];
for(int i=1;i<=n;i++)
{
char ch;
int x,y;
cin>>ch>>x>>y;
r[ch-'A'].a=x;
r[ch-'A'].b=y;
}
string s;
while(cin>>s)
{
s.insert(0,"(");
s.append(")");
stack<Type> q;
int ans(0);
bool success(true);
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
q.push(Type(-1,0));
else if(s[i]==')')
{
Type t;
if(!q.empty() && q.top()!=Type(-1,0))
{
t.a=q.top().a;
t.b=q.top().b;
}
while(!q.empty() && q.top()!=Type(-1,0))
{
q.pop();
if(!q.empty() && q.top()!=Type(-1,0))
{
if(q.top().b!=t.a)
{
success=false;
break;
}
else
{
ans+=q.top().a*q.top().b*t.b;
t.a=q.top().a;
}
}
}
q.pop();
q.push(t);
}
else
q.push(Type(r[s[i]-'A'].a,r[s[i]-'A'].b));
}
if(success)
cout<<ans<<endl;
else
cout<<"error"<<endl;
}
return 0;
}
posted on 2011-04-12 22:34
lee1r 阅读(705)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：字符串处理 、
题目分类：数据结构