用棧，每次遇到右括號就把從左括號到右括號之間的部分全部計算。要在讀取字符串的時候左邊加一個左括號，右邊加一個右括號（一開始沒有這么做依然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 閱讀(745)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：字符串處理 、
題目分類：數據結構