CF7E.Defining Macros

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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".

大多数 C/C++ 程序员都了解预处理器 #define 指令所提供的强大功能;但许多人也同样清楚,若不加小心地使用这些指令,就可能引发各种问题。

本题中,我们考虑如下形式的 #define 构造(也称为宏)。每个宏都有其名称和值。声明宏的通用语法如下:

#define macro\_name macro\_value

宏一旦被声明,在程序中每次出现 "macro\_name" 时,它都会被替换为 "macro\_value"(仅完整词元会被替换;即只有当 "macro\_name" 被空格或其他非字母字符包围时,才会发生替换)。在本模型中,"macro\_value" 只能是一个算术表达式,该表达式由变量、四种基本算术运算符、括号,以及此前已声明的宏名(此时宏替换按声明顺序依次进行)组成。将宏替换成其值的过程称为代入(substitution)

使用宏时出现的主要问题之一是:代入后所得算术表达式的计算顺序因各运算符优先级不同而发生改变。

我们来看如下示例。假设我们声明了如下 #define 构造:

#define sum x + y

随后在程序中计算表达式 "2 * sum"。经宏代入后,我们得到 "2 * x + y",而非直观预期的 "2 * (x + y)"

我们将如下情形称为可疑(suspicious):在宏代入之后,计算顺序发生了改变,且该改变超出了某个宏所覆盖的范围。因此,你的任务是:根据给定的一组 #define 定义及一个给定表达式,判断该表达式是否为可疑表达式。

我们更形式化地描述如下:首先,需对给定表达式执行普通宏代入;其次,还需对该表达式执行一次安全宏代入——即在每次代入宏值时,均将其整体用括号括起;然后,依据算术中的括号展开规则,可省略其中部分括号。若存在某种方式,使得最终得到的表达式与普通代入结果完全一致(逐字符匹配,忽略空格),则称该表达式及其宏系统为正确的(correct);否则,即为可疑的(suspicious)

注意:本题中将 / 运算符视为常规数学除法,而非 C/C++ 中的整数除法。因此,例如在表达式 "a*(b/c)" 中,我们可以省略括号,得到 "a*b/c"

输入格式

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 109.

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.

第一行包含唯一一个数字 nn0n1000 \leq n \leq 100)——表示给定程序中 #define 宏定义的数量。

接下来有 nn 行,每行恰好包含一个 #define 宏定义。每个宏定义具有如下语法:

#define name expression

其中:

  • name —— 宏的名称;
  • expression —— 该宏将被替换为的表达式。表达式是一个非空字符串,仅包含数字、变量名、先前已声明的宏名、圆括号以及运算符 +, -, *, /。保证该表达式(在宏展开前与展开后)均为合法的算术表达式,且不包含一元运算符。表达式中仅包含不超过 10910^9 的非负整数。

所有名称(包括 #define 宏定义的名称及其参数名)均由大小写敏感的拉丁字母组成。保证任意变量名均不同于任意一个 #define 宏定义的名称。

随后,最后一行包含一个待检查的表达式。该表达式非空,且满足与 #define 宏定义中表达式相同的限制条件。

输入各行中可在任意位置出现任意数量的空格,但这些空格不得破坏单词 define 或宏定义及变量的名称。特别地,# 符号前后可有任意数量的空格。

输入文件中任意一行的长度均不超过 100 个字符。

输出格式

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

如果表达式符合上述给定的判定准则,则输出“OK”,否则输出“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

输入解题思路,AI测评打分。不知道怎么写?

首页