UC知道程序设计紧急求助
来源：百度知道 编辑：UC知道 时间：2024/05/07 16:08:53
请高手帮我编一个程序
规则是 ：
1 空序列是规则序列
2 如果S是规则序列那（S）和[S]也是规则序列
3 如果A和B是规则序列则AB也是规则序列
现在给出一些由‘（’ ‘）’ ‘[’ ‘]’构成的序列
请添加尽量少的括号得到一个规则序列
使用语言工具尽量使用C语言或VC，算法为动态规划算法或递归算法。
谢谢各大高手给出指点。
规则是 ：
1 空序列是规则序列
2 如果S是规则序列那（S）和[S]也是规则序列
3 如果A和B是规则序列则AB也是规则序列
现在给出一些由‘（’ ‘）’ ‘[’ ‘]’构成的序列
请添加尽量少的括号得到一个规则序列
使用语言工具尽量使用C语言或VC，算法为动态规划算法或递归算法。
谢谢各大高手给出指点。
设∑={0,...,1,a,...,z,A,...,Z},*表示集合的闭包
S = ∑*
则根据楼主给定规则得到的正规文法为
((S)|[S])*
因为需要画图，这里无法帖，只需楼主将正规文法转化为确定有限自动机(DFA)，然后就可以根据DFA的状态转换图写出一个高效的程序。