ccf-csp 201912-3 化学方程式

Posted on | In | | Visitors:
Words count in article: 528

ccf-csp 201912-3 化学方程式

第一次做好吃力，学完编译原理之后感觉豁然开朗 :-)

严格按照题中所给的BNF形式化定义来写代码，如下图

ri69SI.png

当然其中一些比较小的东西（比如uppercase,lowercase之类的），直接检测了吧，其他的一个一个编写函数来匹配，就是递归下降法的思路，下面是代码部分，看函数名应该很好懂，元素和元素的个数我使用map存的，一是检索起来方便，而是字符串有序，比较起来方便（从头到尾比较，依次比较元素名和元素个数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<map>
#include<string>
using namespace std;
void expr(map<string, int>& e);
int coef();
void formula(map<string, int>& e);
void term(map<string, int>& e);
void element(map<string, int>& e);

char c;	// 当前字符
void expr(map<string, int> &e) {
	map<string, int> temp;
	int num;
	while (c != '=' && c != '\n') {
		temp.clear();
		num = coef();
		formula(temp);
		for (map<string, int>::iterator x = temp.begin(); x != temp.end(); x++) {
			e[x->first] += num * x->second;
		}
		if (c == '+')
			c = getchar();
	}
}
int coef() {
	int ans = 0;
	while (c >= '0' && c <= '9') {
		ans = 10 * ans + c - '0';
		c = getchar();
	}
	if (ans == 0)
		return 1;
	else
		return ans;
}
void formula(map<string, int> &e) {
	int num;
	map<string, int> temp;
	while ((c <= 'Z' && c >= 'A') || c == '(' || (c <= 'z' && c >= 'a')) {
		temp.clear();
		term(temp);
		num = coef();
		for (map<string, int>::iterator x = temp.begin(); x != temp.end(); x++) {
			e[x->first] += num * x->second;
		}
	}
}
void term(map<string, int>& e) {
	if (c == '(') {
		c = getchar();
		formula(e);
		c = getchar();
	}
	else {
		element(e);
	}
}
void element(map<string, int> &e) {
	string name(1, c);
	c = getchar();
	while (c <= 'z' && c >= 'a')
	{
		name.push_back(c);
		c = getchar();
	}
	e[name] = 1;
}
int main() {
	map<string, int> left, right;
	map<string, int>::iterator l, r;
	int n, flag = 1;
	cin >> n;
	c = getchar();
	for (int i = 0; i < n; i++) {
		flag = 1;
		left.clear();
		right.clear();
		c = getchar();
		expr(left);
		c = getchar();
		expr(right);
		if (left == right)
			cout << "Y" << endl;
		else
			cout << "N" << endl;
	}
	return 0;
}