作者miname (Vanish)
看板ACMCLUB
标题第五题:ACM171
时间Sat Dec 28 15:38:18 2002
171的题意是给你一堆rules和字串让你判断字串是否为合法
解法一:
instruction=navigational|time-keeping|navigational AND time-keeping
可替换成
┌>navigational AND time-keeping─┐
起点─>navigational──────────>end
└>time-keeping─────────-┘
其中的navigational又以题目给的条件
navigational=directional|navigational AND THEN directional
替换成
┌<─AND THEN<─┐
起点─>directional──>end
只要能让输入恰从起点走到终点即为合法的解
反之为不合法的解
解法二:
开一个stack每读一个input就判断是否在rule上可替换ex:257可换成nnn
或该input和stack顶的东西可以替换成别的东西
若皆不行则把该input放到stack顶
读完全部input之後stack若不是只剩下navigational就是不合法的input
--
※ 发信站: 批踢踢实业坊(ptt.csie.ntu.edu.tw)
◆ From: 218.187.86.213