题目地址：Codeforces：Problem – 7E – Codeforces、洛谷：CF7E Defining Macros – 洛谷 | 计算机科学教育新生态

题目描述

Most C/C++ programmers know about excellent opportunities that preprocessor #define directives give; but many know as well about the problems that can arise because of their careless use.

In this problem we consider the following model of #define constructions (also called macros). Each macro has its name and value. The generic syntax for declaring a macro is the following:

#define macro_name macro_value

After the macro has been declared, “macro_name” is replaced with “macro_value” each time it is met in the program (only the whole tokens can be replaced; i.e. “macro_name” is replaced only when it is surrounded by spaces or other non-alphabetic symbol). A “macro_value” within our model can only be an arithmetic expression consisting of variables, four arithmetic operations, brackets, and also the names of previously declared macros (in this case replacement is performed sequentially). The process of replacing macros with their values is called substitution.

One of the main problems arising while using macros — the situation when as a result of substitution we get an arithmetic expression with the changed order of calculation because of different priorities of the operations.

Let’s consider the following example. Say, we declared such a #define construction:

#define sum x + y

and further in the program the expression “2 * sum” is calculated. After macro substitution is performed we get “2 * x + y”, instead of intuitively expected “2 * (x + y)”.

Let’s call the situation “suspicious”, if after the macro substitution the order of calculation changes, falling outside the bounds of some macro. Thus, your task is to find out by the given set of #define definitions and the given expression if this expression is suspicious or not.

Let’s speak more formally. We should perform an ordinary macros substitution in the given expression. Moreover, we should perform a “safe” macros substitution in the expression, putting in brackets each macro value; after this, guided by arithmetic rules of brackets expansion, we can omit some of the brackets. If there exist a way to get an expression, absolutely coinciding with the expression that is the result of an ordinary substitution (character-by-character, but ignoring spaces), then this expression and the macros system are called correct, otherwise — suspicious.

Note that we consider the “/” operation as the usual mathematical division, not the integer division like in C/C++. That’s why, for example, in the expression “a*(b/c)” we can omit brackets to get the expression “a*b/c”.

题意简述

给定$n$条宏定义和一个表达式，求编译时给定表达式是否安全。

表达式的安全指宏展开时不会出现与预期不符的结果，例如定义宏#define sum x+y后，对表达值sum*z展开，得到的结果并非(x+y)*z而是x+(y*z)。

更加详细的说明请参考原题面。

输入输出格式

输入格式：

The first line contains the only number n (0 ≤ n ≤ 100) — the amount of #define constructions in the given program.

Then there follow n lines, each of them contains just one #define construction. Each construction has the following syntax:

#define name expression

where

• name — the macro name,
• expression — the expression with which the given macro will be replaced. An expression is a non-empty string, containing digits,names of variables, names of previously declared macros, round brackets and operational signs +-*/. It is guaranteed that the expression (before and after macros substitution) is a correct arithmetic expression, having no unary operations. The expression contains only non-negative integers, not exceeding 10⁹.

All the names (#define constructions’ names and names of their arguments) are strings of case-sensitive Latin characters. It is guaranteed that the name of any variable is different from any #define construction.

Then, the last line contains an expression that you are to check. This expression is non-empty and satisfies the same limitations as the expressions in #define constructions.

The input lines may contain any number of spaces anywhere, providing these spaces do not break the word “define” or the names of constructions and variables. In particular, there can be any number of spaces before and after the “#” symbol.

The length of any line from the input file does not exceed 100 characters.

输出格式：

Output “OK”, if the expression is correct according to the above given criterion, otherwise output “Suspicious”.

输入输出样例

输入样例#1：

1
#define sum x + y
1 * sum

输出样例#1：

Suspicious

输入样例#2：

1
#define sum  (x + y)
sum - sum

输出样例#2：

OK

输入样例#3：

4
#define sum  x + y
#define mul  a * b
#define div  a / b
#define expr sum + mul * div * mul
expr

输出样例#3：

OK

输入样例#4：

3
#define SumSafe   (a+b)
#define DivUnsafe  a/b
#define DenominatorUnsafe  a*b
((SumSafe) + DivUnsafe/DivUnsafe + x/DenominatorUnsafe)

输出样例#4：

Suspicious

题解

一看就是一道细节巨多很难写的hack大模拟题。我们讨论所有表达式的可能性：

1. 不包含任何运算符 – 取决于表达式展开后是否安全，若只包含一个变量则安全
2. 被一对括号包围 – 取决于括号内的表达式是否安全
3. 计算顺序最末的符号为加减号 – 出现在减号后面或者乘除号的前面或后面都不安全，其余情况安全
4. 计算顺序最末的符号为乘除号 – 出现在除号后面不安全，其余情况安全

因此可以按照安全程度对安全性分类：不安全、在减号后面或者乘除号的前面或后面都不安全 、在除号后面不安全、安全，分别用0 1 2 3代表这四类。

考虑对一个表达式进行分治解决：找到末尾第一个加减号，将前半部分和后半部分分治求解，并组合分治的结果，如果前部分或后部分不安全，或符号为减号的情况下后部分不安全，则整个式子不安全，否则安全性为1；之后再找末尾第一个乘除号，如果前或后部分安全性为0或1，或符号为除号的情况下后部分不安全，则整个式子不安全，否则式子安全性为2；被括号括起来的式子，只有0和3两种安全性；只包含一个变量名的表达式安全性为3……以此类推，处理完所有的情况即可得到正解。

另外输入可能存在多余的空格，需要及时除掉，#和define也不一定连在一起，需要找define处理。

这个题卡了好久，第一次写了纯暴力判断TLE 134，后来参考了题解[Codeforces 7E] Defining Macros – NewErA – 博客园（感谢原作者）重构代码，又因为细节WA了好多次，今天终于解决了，以下是提交记录截图。

代码

// Code by KSkun, 2019/8
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

const int MAXN = 105;

struct Macro {
	std::string name, expr;
} m[MAXN];

int n;
std::string expr;
std::map<std::string, int> lvl;

inline bool isop(char c) {
	return c == '+' || c == '-' || c == '*' || c == '/';
}

inline void parse(std::string line, Macro& m) {
	int res = line.find("define"), l = res + 6, r, len = line.length();
	while(l < len && line[l] == ' ') l++; r = l;
	while(r < len && line[r] != ' ') r++;
	m.name = line.substr(l, r - l);
	while(r < len && line[r] == ' ') r++;
	m.expr = line.substr(r);
}

int process(std::string str) {
	// remove front/back blanks
	int l = 0, r = str.length() - 1;
	while(l < str.length() && str[l] == ' ') l++;
	while(r >= 0 && str[r] == ' ') r--;
	str = str.substr(l, r - l + 1);

	// default
	int cnt = 0;
	for(int i = str.length() - 1; i >= 0; i--) {
		if(str[i] == ')') cnt++;
		if(str[i] == '(') cnt--;
		if((str[i] == '+' || str[i] == '-') && cnt == 0) {
			int res1 = process(str.substr(0, i)), 
				res2 = process(str.substr(i + 1, str.length() - i + 1));
			if(res1 == 0 || res2 == 0) return 0;
			if(str[i] == '+') return 1;
			if(str[i] == '-') return res2 == 1 ? 0 : 1;
		}
	}

	cnt = 0;
	for(int i = str.length() - 1; i >= 0; i--) {
		if(str[i] == ')') cnt++;
		if(str[i] == '(') cnt--;
		if((str[i] == '*' || str[i] == '/') && cnt == 0) {
			int res1 = process(str.substr(0, i)),
				res2 = process(str.substr(i + 1, str.length() - i + 1));
			if(res1 <= 1 || res2 <= 1) return 0;
			if(str[i] == '*') return 2;
			if(str[i] == '/') return res2 == 2 ? 0 : 2;
		}
	}
	
	// brakets surrounded
	if(str.front() == '(' && str.back() == ')')
		return process(str.substr(1, str.length() - 2)) == 0 ? 0 : 3;

	// contain no operator
	return lvl.find(str) != lvl.end() ? lvl[str] : 3;
}

int main() {
	std::cin >> n;
	std::string line;
	std::getline(std::cin, line);
	for(int i = 1; i <= n; i++) {
		std::getline(std::cin, line);
		parse(line, m[i]);
		lvl[m[i].name] = process(m[i].expr);
	}
	getline(std::cin, expr);
	int res = process(expr);
	if(res == 0) puts("Suspicious");
	else puts("OK");
	return 0;
}