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

判断宏是否是“安全”的

 
阅读更多
给了一系列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".
分享到:
评论

相关推荐

    excel编写的身份证号码校验程序

    excel编写的身份证号码校验程序,只要将身份证号码与性填写到相应的表格项中就可知道身份证号码是否正确。注意使用时需要将execl中“工具”-“选项”-“安全性”-“宏安全性”设置为低才可以运行。

    计算身份证号合法性、重复批量判断 (窗口版) .xlsm

    word2010以上版本使用,该程序可以实现批量身份证合法性判断,需要启用宏安全才能运转,需要先准备好身份证数据的一张电子表格,必须将身份证数据放在F列,F列后面的位置留空,计算结果将在F列后显示。

    计算机网络安全基础试题及答案..doc

    计算机网络安全基础试题及答案 2008年01月09日 22:03 第一章: 1,信息安全定义:为了防止对知识,事实,数据或功能未经授权而使用,误用,未经 授权修改或拒绝使用而采取的措施。 第二章 1,攻击的类型:访问攻击(信息...

    信息科科室安全检查记录表(vba插入工作日记录)

    '判断指定日期是否上班 Function workDay(rq) Dim cel As Range If Weekday(rq) = 1 Or Weekday(rq) = 7 Then temp = "休" For Each cel In Range("节假日表!B2:B17") a = DateDiff("d", cel.Value, rq) If a ...

    checklist 学习资料 学习资料

    17 缓冲区溢出安全问题检查 是否存在诸如 strcpy/strcat/scanf 此类高危险性缓冲区溢出函数,使用是否存在问题。 字符串操作函数的长度计算必须确保正确 注意空字符结束的函数,如strncat,有时会自动在内存后面添加...

    网络安全作业.doc

    1. 判断题 1.Windows系统活动目录包括目录和与目录相关的服务两个部分。 2.AES算法的每轮变换由四种不同的变换组合而成,它们分别是S- 盒变换、行位移变换、列混合变换和圈密钥减法变换。 3.hash函数的特点是:...

    网络安全与计算机病毒.doc

    因 此是否具有传染性被作为判断程序是否是计算机病毒的首要条件。 2. 潜伏性。设计精巧的计算机病毒在进入计算机系统后通常会较长时间潜伏,除了伺机 传染之外,不进行任何特征明显的破坏活动,以保证有充裕的时间...

    SystemSecurity-ReverseAnalysis:该资源为系统安全和逆向分析实验,包括作者从零学习恶意代码分析,病毒逆向分析的工具及样本,基础性文章,希望对您有所帮助〜

    宏病毒邮件恶意攻击+补充宏病毒攻击复现[系统安全]二十三。逆向分析之OllyDbg动态调试基础复习及TraceMe案例分析[系统安全]二十四。逆向分析之OllyDbg逆向CrackMe01-02及加壳判断[系统安全]二十五。逆向分析之Oll

    YXCTool:日常开发中一些用得到的代码整理

    HEIGHT当前设备屏幕的高度IPHONE_WIDTH当前设备屏幕的宽度kIsBangsScreen判断当前设备是否是刘海屏幕NSArray +崩溃主要是对NSArray , NSMutableArray一些数据安全做一层判断,降低因为数据异常导致崩溃的概率具体...

    Visual C++开发经验技巧宝典(第4章)

    0191 判断某个句柄是否关联一个窗口 95 0192 MFC应用程序信息和管理函数 95 0193 Internet URL解析全局函数 95 4.3 MFC框架技术 96 0194 在类的定义时使其具有运行时类型识别的功能 96 0195 运行时判断...

    Excel VBA技巧实例手册

    技巧007设置宏的安全性 第2章 使用VBE工具 2.1 设置VBE环境 技巧008设置VBE窗口 技巧009设置VBE的属性 2.2 编辑模块 技巧010添加模块 技巧011删除模块 技巧012导出模块 技巧013导入模块 2.3 使用VBE的编码功能 ...

    电子注册加密解决方案

    *本方案提供宏调用形式的加密方案,保证源码级加密,增加crack的难度。 *系统中合法性检查提供各种延迟处理方案,让crack更加复杂,不定时检查将更好的保证我们的软 件成果。 再强的加密也总有破解的方法,因此本...

    基于岩体宏细观特征的大型帷幕注浆保水开采技术及应用-论文

    细观上基于显微CT分析研究受注介质空隙发育特征和几何参数,宏细观结合综合分析大型帷幕墙体建造科学位置、钻探工艺、注浆材料和适用性配比选取、注浆压力等问题,并利用放水试验、钻孔取芯、钻屑组分判断等手段对...

    《你必须知道的495个C语言问题》

    3.7 是否可以安全地认为,一旦&&和||左边的表达式已经决定了整个表达式的结果,则右边的表达式不会被求值? 36  3.8 为什么表达式printf("%d %d", f1(), f2()); 先调用了f2?我觉得逗号表达式应该确保从左到右的...

    你必须知道的495个C语言问题

    3.7 是否可以安全地认为,一旦&&和||左边的表达式已经决定了整个表达式的结果,则右边的表达式不会被求值? 3.8 为什么表达式printf("%d%d",f1(),f2());先调用了f2?我觉得逗号表达式应该确保从左到右的求值顺序...

    基石电子注册SDK

    基石 ERegToolbox 是一个帮助软件开发者开发安全可靠、不轻易被Cracker破解的共享软件的SDK。 本SDK提供DLL & Lib & .H的形式给软件开发者使用。 本SDK在内部实现了对共享软件产品最终用户的计算机硬件信息进行...

    精通WindowsAPI 函数 接口 编程实例

    4.2.3 判断光驱中是否有光盘 81 4.2.4 获取磁盘分区的总容量、空闲容量、簇、扇区信息 83 4.3 文件和目录管理 86 4.3.1 删除、复制、重命名、移动文件 87 4.3.2 创建、打开、读写文件,获取文件大小 90 ...

    kerberos报告1

    声明了如下宏和函数:客户端主函数结构如下:* @return sockaddr_in 结构体* 判断响应是否有效* @param response char*

Global site tag (gtag.js) - Google Analytics