魔王语言解释.docx

数据结构课程设计文档
魔王语言解释 (线性)
[ 问题描述 ]
有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话,没有人能听得懂,但他的语
言是可以逐步解释成人能听懂的语言,因为他的语言是由以下两种形式的规则由人的语言逐
步抽象上去的:
(1) α -> β 1β 2, β m
(2)( θ δ1δ2, δn) - >θ δnθδn-1, θδ 1θ
在这两种形式中,从左到右均表示解释。试写一个魔王语言的解释系统,把他的话解释成人
能听得懂的话。
[ 基本要求 ]
用下述两条具体规则和上述规则形式( 2)实现。设大写字母表示魔王语言的词汇;小写字
母表示人的语言词汇;希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含
人的词汇。
(1)B - > tAdA
(2)A - > sae
[ 测试数据 ]
B(ehnxgz)B 解释成 tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系,则魔王说的话是:“天上一只鹅地上一只鹅
鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
t d s a e z g x n h
天 地 上 一只 鹅 追 赶 下 蛋 恨
一:需求分析
(1) 以一维数组 demon[ i ] 表示魔王语言.
(2) 魔王语言由用户输入 , 初始保存在 demon[ i ] 中.
(3) 魔王语言与人类语言对应关系固化在程序中.
(4) 实现过程:
A:初始,魔王语言接收后存放在 demon[ i ] 中.
B:初次遍历数组,将数组中括号内的元素入栈,同时插入相应首字母;
C:再次遍历数组,将数组元素依次入队。(小写字母直接入队;大写字母经翻译成相应字
符后入队;遇到括号,将栈中保存的元素依次出栈入队)在翻译过程中,如果依旧包含大写
字母,则置 flag 为 1,否则为 0。
D:将队列中元素赋值给 demon[ i ] 。如果此时 flag=1 ,则再次重复 C 过程。直至所有元素
为人类语言。
E:输出 demon[ i ] 。此时数组中元素为对应的人类语言。注:如果程序中没有相应的对应
关系,则翻译成“ ???”。
二:概要设计 :
1:设定栈的抽象数据类型定义:
ADT stack {
数据对象: D={ ai|ai ∈CharSet,i = 1,2, , ,n,n>=0 }
数据关系: R1={<ai-1,ai>|ai-1,ai ∈D,i = 2, , ,n}
基本操作:
initstack ( &s)
操作结果 : 构造一个空栈 s.
push ( & s,e)
初始条件 : 栈 s 已存在 .
操作结果 : 在栈 s 的栈顶插入新的栈顶元素 e.
pop( &s, &e)
初始条件 : 栈 s 已存在 .
操作结果 : 删除 s 的栈顶元素 , 并以 e 返回其值 .
}ADT stack
2: 设定队列的抽象数据类型 :
ADT queue{
数据对象: D={ ai|ai ∈Elemset,i = 1,2, , ,n,n>=0 }
数据关系: R1={<ai-1,ai>|ai-1,ai ∈D,i = 2, , ,n}
基本操作:
initqueue(&q)
操作结果 : 构造一个空队列 q.
enqueue(&q, e)
初始条件 : 队列 q 已存在 .
操作结果 : 插入元素 e 为 q 的新队尾元素 .
dequeue(&q,&e)
初始条件 : q 为非空队列 .
操作结果 : 删除 q 的队头元素 , 并用 e 返回其值 .
}ADT queue
3: 本程序包含四个模块 :
1) 主函数模块 . 其中主函数为 :
status main()
{
初始化栈 ;
初始化队列 ;
接收魔王语言输入到数组 demon[i ];
遍历数组将括号中元素进栈 ;
while( 数组 demon[i ] 中元素有大写字母 )
{ 翻译排序处理后入队列 ;
将对列元素保存在数组 demon[i ];
}
输出人类语言 ( 数组 demon[ i]);
}
2) 括号内元素入栈处理模块 .
tempstack(&temps)
将括号内元素入栈 , 依次插入首字符 .
举例: (abcd) ->adacaba.
3) 排序入队列模块 .
sort(&s,&q)
{
遍历数组 ;
{
遇到小写字母 , 直接入队列 ;
遇到大写字母 , 翻译大写后入队列 ;
遇到括号 , 将栈中保存的元素依次出栈入队列 ;
}
}
4) 翻译大写处理模块 .
spenque