判断宏是不是是“安全”的
判断宏是否是“安全”的
<!--StartFragment -->
给了一系列C++的宏定义，问你一个表达式是否是“安全”的。安全的定义是，展开后的表达式中，所有的宏在计算过程中都被作为一个整体运算。
如#definesumx+y后，2∗sum就会被替换乘2∗x+y，此时因为乘号优先级比加号高，导致sum宏在实际计算中被拆开了，可能产生错误。
宏的个数≤100,每个表达式长度≤100.只有四则运算和括号。
如#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)
•状态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".
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".