FZYZOJ 2098 混合物计量 【字符串处理+栈】

tonyfang posted @ 2015年9月04日 17:20 in FZYZOJ with tags C++ OI , 285 阅读

P2098 -- 混合物计量

时间限制:1000MS

内存限制:262144KB

Description

给一些化合物。求出这些化合物中,各种原子的个数分别是多少?

和本题有关的化学知识(已经了解的可以跳过):

(1)原子:用一个大写字母或一个大写字母和一个小写字母表示,比如C或Fe,只要是这种格式,都为原子。

(2)物质:用原子和数字表示,每一个原子后面的数字表示该原子的数量(没有数字表示为1个)如O2表示有两个O原子;H2O表示由2个H和1个O;H2CO3表示有2个H、1个C、3个O。如果有括号,括号后面的数字表示括号里面整体的数量(没有数字表示为1个),比如(((O)2)2)2表示8个O,Ca(OH)2表示1个Ca、2个O和2个H。

(3)物质前面的数字:如3CaCO3表示3份CaCO3,就是3*1个Ca、3*1个C和3*3个O。3Ca(OH)2就是3个Ca,6个O和H

本题中,化合物只会出现大小写字母、数字和左右括号。

Input Format

第一行一个整数n,表示物质的数量。

下面n行,每行一个物质,如3CaCO3或Ca(OH)2。

Output Format

输出一行,每一行格式为“A=a”,A为原子,a表示A原子出现的个数,如“Na=1”。

按照原子名称的字典序,先输出单个字母的原子,再输出两个字母的原子。

Sample Input

2
CO2
CO2

Sample Output

C=2
O=4

Hint

n不大于100,000。每一行不大于1000字节。

 

保证每种原子个数不超过2^63-1。

【题解】

好吧我承认我太弱了~

首先,逆序处理,把单个元素也加上括号。

栈里面存的是当前的系数(包括括号外的)

随便维护下~

然后数据十分坑。

数据会有系数为0的情况~改成1

没了。。

狂 WA 不止

然后试了试cin.sync_with_stdio(false);发现并没有用。

 

# include <stdio.h>
# include <iostream>
# include <cctype>
# include <stack>
using namespace std;
string str;
int getnum(char a,char b=0) {
	if(b) return 26 * (a - 'A' + 1) + (b - 'a');
	else return a - 'A';
}
long long ans[1001];
int n;
stack <long long> st;
inline void sget(string s, int tonum) {
	bool u = 0;
	for (int i = s.size() - 1; i >= tonum; --i) {
		if (isdigit(s[i])) {
			int j = i, tt;
			while(isdigit(s[j - 1])) --j;
			tt = j;
			long long nums = 0;
			for (; j <= i; ++j) nums = nums * 10 + s[j] - '0';
			if (nums == 0) nums = 1;
			i = tt;
			long long lasty = st.top();
			nums *= lasty;
			st.push(nums);
			u = 1;
		}
		if (s[i] == '(') st.pop();
		if (s[i] == ')') {
			u = 0;
			if (! isdigit(s[i + 1])) {
				int _top;
				_top = st.top();
				st.push(_top);
			}
		}
		if (isalpha(s[i])) {
			if(islower(s[i])) {
				int nums = getnum(s[i-1], s[i]);
				--i;
				ans[nums] += st.top();
			} else ans[getnum(s[i])] += st.top();
			if(u) {
				st.pop();
				u = 0;
			}
		}
	}
}
inline void sets(string s) {
	int pre = 1;
	int i = 0;
	if (isdigit(s[0])) {
		pre = s[0] - '0';
		while (isdigit(s[i + 1])) 
			pre = pre * 10 + s[++ i] - '0';
		++i;
	}
	while(!st.empty()) st.pop();
	st.push(pre);
	sget(s, i);
}
inline void outs() {
	for (int i = 0; i < 1000; ++i) 
		if(ans[i])
			if(i < 26) printf("%c=%lld\n", i + 'A', ans[i]);
			else printf("%c%c=%lld\n", i / 26 - 1 + 'A', i % 26 + 'a', ans[i]);
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	while (n--) {
		cin >> str;
		sets(str);
	}
	outs();
	return 0;
}

登录 *


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