`
guoyiqi
  • 浏览: 1010928 次
社区版块
存档分类
最新评论

判断宏是否是“安全”的

 
阅读更多
给了一系列C++的宏定义,问你一个表达式是否是“安全”的。安全的定义是,展开后的表达式中,所有的宏在计算过程中都被作为一个整体运算。
如#definesumx+y后,2∗sum就会被替换乘2∗x+y,此时因为乘号优先级比加号高,导致sum宏在实际计算中被拆开了,可能产生错误。
宏的个数≤100,每个表达式长度≤100.只有四则运算和括号。
木其工作室 qq:928900200
我们考虑一个宏是否是“安全”的,经过观察和一些实验,可以发现,只有以下4种状态:
•状态1(s1):这个宏完全安全,以任何方式使用该宏都没问题。
•状态2(s2):这个宏不安全,只要表达式中出现该宏,都会导致表达式不安全。
•状态3(s3):这个宏部分安全,仅当这个宏与’*’,’/’连接时,或出现在’-’后面时,才会使表达式不安全。
•状态4(s4):这个宏部分安全,仅当这个宏出现在’/’后面时,才会使表达式不安全。有了这4个状态,我们只需推出状态之间的转移即可。
•如果表达式没有使用任何运算符或括号或宏(也就是s仅仅是个单独的变量),那么安全级别显然是s1
•如果表达式s是(t)的形式(被一对括号括起来的表达式t),那么如果t的状态不是s2,则s的状态是s1,否则s的状态是s2
•我们找到表达式s中,最后一次运算的符号,设其为op,设其两侧表达式分别为t1和t2。我们进行以下分类讨论:
–显然,如果t1或t2的安全状态是s2,则s的状态也是s2;–如果op是’+’,那么s的状态是s3;
–如果op是’-’,那么,如t2状态是s3,则s状态是s2,否则s状态是s3
–如果op是’*’,那么,如t1或t2状态是s3,则s状态是s2,否则s状态是s4
–如果op是’/’,那么,如t1或t2状态是s3,或t2状态是s4,则s状态是s2,否则s状态是s4于是,此题得到了解决。时间复杂度O(n∗len2),如果愿意追求更好的复杂度,可以建出表达式树,从而做到O(N∗len)
 

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


Input

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


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

Output "OK", if the expression is correct according to the above given criterion, otherwise output "Suspicious".
分享到:
评论

相关推荐

    MFC宏定义详解讲述宏的定义

    - **使用`__cplusplus`和`_AFXDLL`宏**:这些宏可以帮助判断是否在C++环境中或者使用了MFC动态链接库。 7. **替代宏的方法**:随着C++的发展,一些宏的功能可以通过模板、函数重载、`constexpr`等现代C++特性实现...

    csgo鼠标宏,lua格式

    6. **安全与合法性**:值得注意的是,使用鼠标宏在某些情况下可能违反CSGO的公平竞赛规则。官方可能会封禁使用非法宏的账号,因此在创建和使用宏时应谨慎。 7. **社区与资源**:许多CSGO玩家会在论坛和社区分享他们...

    宏的使用范例一能够教会您用宏和对宏的操作

    在实际应用中,宏的安全设置需谨慎处理,因为不当的宏可能引入病毒或恶意软件。 总的来说,宏的使用范例一通过创建抽奖系统展示了宏在自动化工作流程、简化复杂任务方面的巨大潜力。通过学习和实践,无论是初级用户...

    adcancedKey 键盘宏录制

    可以添加延迟、条件判断、循环等逻辑,使得宏更加灵活。 4. **回放宏**:播放宏时,软件按照录制的顺序执行每一个动作,精确无误,提高工作效率。 5. **应用领域**: - **游戏**:在需要重复动作的游戏中,例如...

    EXCEL233个常用宏

    3. **宏的安全性**:由于宏可以执行任意代码,所以Excel默认设置为禁用未知源的宏,以防止恶意软件。在使用宏前,需要在信任中心设置中调整安全级别。 4. **宏的基本结构**:一个宏通常由Sub过程或Function过程组成...

    EB8000宏指令说明书

    整体而言,EB8000宏指令说明书为用户提供了一个全面了解和掌握宏指令应用的平台,从基础的语法结构到高级应用,从编辑工具到安全保护,都有详尽的介绍和指导,使得宏指令的开发和应用变得更加直观和高效。...

    Excel-VBA宏编程实例源代码-判断工作表中是否设置了筛选.zip

    在这个“Excel-VBA宏编程实例源代码-判断工作表中是否设置了筛选.zip”压缩包中,包含了一个名为“判断工作表中是否设置了筛选.xlsm”的文件,这是一个VBA宏代码示例,专门用于检测工作表是否启用了筛选功能。...

    一样的宏,不同的结果

    6. **宏代码本身**:尽管看起来宏代码相同,但在代码中可能存在条件判断或特定的环境检测,使得宏在不同环境下表现出不同行为。 要解决这个问题,可以按照以下步骤进行排查: 1. **检查安全设置**:确保两台电脑的...

    宏语言,宏程序,基础讲解,入门讲解

    8. 宏程序的安全性问题:宏程序的安全性问题包括程序的错误、程序的破坏和数据的泄露等。因此,宏程序的安全性问题需要引起足够的重视。 9. 宏程序的发展趋势:宏程序的发展趋势包括智能化、网络化和自动化等。随着...

    EXCEL的常用259个常用宏代码

    - 宏安全设置:了解如何在Excel中设置宏的安全级别,防止恶意宏的运行。 - 宏存储:工作簿可以保存为启用宏的工作簿格式(.xlsm),宏会随文件一起保存。 - 宏模块组织:将宏组织到不同的模块中,便于管理和维护...

    Excel-VBA宏编程实例源代码-判断文件夹是否存在,如果不存在就创建新文件夹.zip

    4. **实际应用**: 在"判断文件夹是否存在,如果不存在就创建新文件夹.xlsm"这个例子中,可能的实现是用户运行一个Excel工作簿宏,该宏会检查指定路径下的文件夹是否已存在。如果不存在,宏会自动创建这个文件夹,以...

    宏病毒专杀

    2. **使用专业工具**:"宏病毒专杀"工具就是为此目的设计的,它可以扫描、检测并移除宏病毒,对用户来说更为安全便捷。 3. **恢复系统**:如果病毒已经严重破坏系统,可能需要进行系统还原或重装操作系统。 在安装...

    excel常用的259个宏

    Excel有宏安全设置,允许用户根据需要调整信任级别。 4. **宏的基本结构**:一个宏通常由Sub过程或Function过程组成,前者用于执行一系列操作,后者用于返回值。每个过程包含声明部分(定义变量)、代码部分(实现...

    c/c++宏定义 宏定义的入门教材 基础

    2. **条件判断宏** ```c #define YES 1 #define NO 0 if (x == YES) { printf("%d\n", YES); } else if (x == NO) { printf("%d\n", NO); } ``` 上述代码中,`YES`和`NO`被定义为整数值1和0。通过比较...

    键盘鼠标宏编辑工具(Macro Expert Enterprise) v3.4.9 官方最新版

    用户不仅可以录制宏,还能通过编辑器对宏进行定制,添加条件判断、循环结构等逻辑,使其更加灵活和智能。 **文件名称解析:** - "gm_setup.exe" 很可能是一个安装程序,用于在用户的计算机上安装 Macro Expert ...

    C语言宏定义技巧(常用宏定义)

    在输入验证中,判断字符是否为数字是很常见的需求。可以定义如下宏: ```c #define DECCHK(c) ((c) &gt;= '0' && (c) ) #define HEXCHK(c) (((c) &gt;= '0' && (c) ) || \ ((c) &gt;= 'A' && (c) ) || \ ((c) &gt;= 'a' && (c...

    报告提取经纬度宏工具

    - **条件判断**:在某些情况下,宏可能需要进行条件判断,比如检查数据格式是否正确,是否存在空值等。 - **错误处理**:良好的宏设计会包含错误处理机制,以防遇到不可预见的问题。 此外,为了保证数据安全,使用...

    预处理宏和内联函数的区别

    (x):0) 定义了一个简单的条件判断宏。宏的优点在于它不涉及函数调用的开销,因为它们只是简单的文本替换,不涉及运行时的堆栈管理和参数传递。然而,宏的缺点也很明显,它们不检查类型,可能导致意外的行为,如在...

    word 宏命令大全1

    - 在`F2无格式粘贴到新word并保存关闭`宏中,首先检查是否有选中的文本,然后判断是否需要新建文档。接着,使用`PasteSpecial`方法进行无格式粘贴,并关闭文档。 通过这些宏命令,用户可以定制自己的快捷键,实现...

    EXCEL4.0宏帮助的中文版

    4. **函数和方法**:Excel 4.0宏支持大量的内置函数和方法,如SUM、AVERAGE、IF等,用于数据计算和逻辑判断。同时,还可以创建自定义函数来满足特定需求。 5. **事件处理**:通过宏,用户可以设置事件处理程序,当...

Global site tag (gtag.js) - Google Analytics