1、魔王语言解释程序 一、一、 问题引入问题引入 1. 问题描述 有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的 语言是可以逐步解释成人能懂的语言的， 因为他的语言是由以下两种形式的规则由人的语言 逐步抽象上去的： （1）12m （2）(12m)(m21) 在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能 听懂的话。 2. 基本要求 用下述两种规则和下述规则（2）实现。设大写字母表示魔王语言的词汇，小写字母表 示人的词汇， 希腊字母表示可以用大写字母或小写字母代换的变量。 魔王语言可含人的词汇。 (1) BtAdA (2) Asae 3.
2、测试数据 B(einxgz)B 解释成 tsaedsaeezegexeneietsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是： “天上一只鹅地上一 只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅” 。 t d s a e z g x n h 天 地 上 一只 鹅 追 赶 下 蛋 恨 4实现提示 将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母 顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。 5.本程序采用的是顺序栈。 基本操作列表： (1)据括号的个数设一个标记。记下括号的位置。 (2)根据标记来执行依次的操作。 (3)没
3、有括号，直接进队，据翻译函数 2 输出人的语言。 (4)有括号，分为括号内的和括号外的。 ，根据括号的位置：括号外的从右到左入栈；括号内 的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数 2 出栈并且翻译。 二、需求分析二、需求分析 1. 本演示程序中，魔王语言限制在小写字母a-z之间，且必须限制在括号内以及大 写字母 A 和 B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果 中将不含重复字符和非法字符。 2. 魔王语言遵守如下规则： （123n）nn-11 BtAdA Asae 3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用
4、 户自行选择下一步命令，相应输入数据和运算结果在其后显示。 4. 程序的执行命令有：1）选择操作 2）任意键结束 5. 数据测试 B(ehnxgz)B 解释成：tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是： “天上一只鹅地上一只鹅 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅” 。 t d s a e z g x n h 天 地 上 一只 鹅 追 赶 下 蛋 恨 三、概要设计三、概要设计 为实现上述功能，需要栈和队列两个抽象数据类型。 1. 栈抽象数据类型定义 ADT stack 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2, n 基本操作： InitStack( printf(“nt 按任意键退出nn“); 各子程序模块： /*初始化栈*/void InitStack(SeqStack *s) s-top=-
