Codeforces 7E Defining Macros

正文索引 [隐藏]

传送门:http://codeforces.com/contest/7/problem/E

题目大意

题目给了一系列C++的宏定义,问你一个表达式是否是\安全”的。安全的定义是,展开后的
表达式中,所有的宏在计算过程中都被作为一个整体运算。
如#de ne sum x+y 后, 2  sum就会被替换乘2  x+y,此时因为乘号优先级比加号高,
导致sum宏在实际计算中被拆开了,可能产生错误。
宏的个数 100, 每个表达式长度 100. 只有四则运算和括号。

题解

我们考虑一个宏是否是\安全”的,经过观察和一些实验,可以发现,只有以下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;

  1. 如果op是’+’,那么s的状态是s3;
  2. 如果op是’-‘,那么,如t2状态是s3,则s状态是s2,否则s状态是s3
  3. 如果op是’*’,那么,如t1或t2状态是s3,则s状态是s2,否则s状态是s4
  4. 如果op是’/’,那么,如t1或t2状态是s3,或t2状态是s4,则s状态是s2,否则s状态是s4

于是,此题得到了解决。时间复杂度O(n  len2),如果愿意追求更好的复杂度,可以建
出表达式树,从而做到O(N  len)

代码