[POJ 1421]

Peter’s Calculator

模拟(难)

给出一段程序,要求按照给定的运行方式,对每次PRINT操作判断是否有效,若有效还需求值。

并没有太多算法的题目,但各种细节很多

大致思路就是先将全部程序文本读入,进行预处理:记录每行程序的类型(赋值、打印或重置),并且
(1)如果是赋值,则对被赋值的变量进行编号,并将等号右边的内容以纯文本方式保存下来
(2)如果是打印,则检查被打印的变量之前是否存在相应赋值,若有则记录变量编号,若无则记录编号为-1
(3)如果是重置,无需特殊处理

然后就是求解了,按顺序对每行i进行处理,期间维护一个搜索赋值语句的上下界[es,ee],初始es=ee=0,并且
(1)如果是赋值,忽略
(2)如果是打印,则ee=i-1,并尝试对该变量求值,若成功则打印值,否则打印”UNDEF”
(3)如果是重置,则es=i+1

每次对变量id求值的操作可能涉及其他变量,因此使用递归结构。而要防止循环求值,因此初始化全0数组st[]来记录变量是否在递归栈中。每次递归内部结构大致如下:
(1)若st[id]!=0,直接返回;st[id]=1,按从后往前(从ee到es)的顺序找第一个对va赋值的语句
(2)对将赋值字符串中的所有变量调用递归求值,若某变量求值失败,直接返回
(3)用一个新字符串保存将赋值字符串中所有变量替换为值后的结果(必须不修改原来的赋值字符串),随后使用递归下降分析求解该字符串的值
(4)记录变量的值,st[id]=2

最后求值完毕后,若要打印的变量st[]为2,则表示成功求值。

程序的主要部分想清楚后实现也花了不少时间,最后则是在空格问题上卡了很久。

在POJ上做过最冷门的题目了,算上我也才53个人AC。但貌似数据比较弱哦,总觉得比想象中要顺利得多……