魔王语言解释程序
一、    问题引入
1. 问题描述
有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的
语言是可以逐步解释成人能懂的语言的， 因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（ 1） α →β 1β 2⋯β m
（ 2） ( θ β1β 2⋯ βm)→ ( θβ m⋯ β 2θ β 1θ )
在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能
听懂的话。
2. 基本要求
用下述两种规则和下述规则（    2）实现。设大写字母表示魔王语言的词汇，小写字母表
示人的词汇， 希腊字母表示可以用大写字母或小写字母代换的变量。    魔王语言可含人的词汇。
(1) B  → tAdA
(2) A  → sae
3.    测试数据
B(einxgz)B    解释成  tsaedsaeezegexeneietsaedsae

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：
只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”    。

“天上一只鹅地上一

t

d

s

a

e

z

g

x

n

h

天    地    上
4．实现提示

一只

鹅

追

赶

下

蛋

恨

将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。
5. 本程序采用的是顺序栈。基本操作列表：
(1) 据括号的个数设一个标记。记下括号的位置。
(2) 根据标记来执行依次的操作。
(3) 没有括号，直接进队，据翻译函数2 输出人的语言。
(4) 有括号，分为括号内的和括号外的。  ，根据括号的位置：括号外的从右到左入栈；括号内
的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数    2 出栈并且翻译。
二、需求分析
1. 本演示程序中， 魔王语言限制在小写字母 ‘a’ - ‘z’之间， 且必须限制在括号内以及大写字母 A 和 B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果
中将不含重复字符和非法字符。
2. 魔王语言遵守如下规则：
（ θ δ 1δ 2δ 3⋯δ n）  θ δ nθδ n-1 ⋯ θδ 1θ
B    tAdA    A    sae
3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
4. 程序的执行命令有：  1printf函数括号内参数的构成解说）选择操作  2  ）任意键结束

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。