Skip to content

Instantly share code, notes, and snippets.

@kmahyyg
Created October 10, 2018 09:31
Show Gist options
  • Save kmahyyg/dfa70197a70551690b186f22b178cb27 to your computer and use it in GitHub Desktop.
Save kmahyyg/dfa70197a70551690b186f22b178cb27 to your computer and use it in GitHub Desktop.
DataStru-Code-Explain

Data Structure 03 - Interpreter of Magic Language

Prerequisites

Make sure you've already known it's a case-sensetive interpreter.

If you're a Linux user, you could just ignore this notification.

Linus Torvalds: Your PC is like air-conditioning — it becomes useless when you open Windows.

Difficulties (B)

难度 A: 实现一个魔王语言解释器。根据产生式规则对魔王语言进行翻译。

如:应用规则:

B -> tAdA A -> sae

对魔王的话: B(ehnxgz)B 进行翻译。;个人完成,评分最高 70 分。

alpha -> beta[1] beta[2]...beta[m]

(theta lambda[1] lambda[2] lambda[3]...lambda[n]) -> theta lambda[n] theta lambda[n-1] theta.... lambda[1] theta

难度 B: 在 A 的基础上,(根据产生式)自定义规则,将一段魔王的话翻译为有 意义的人类语言(中文);个人完成,评分最高至 90 分。

Test Data

难度 A:

输入 B(ehnxgz)B

输出 t A d A

[ t <sae> d <sae> ] ez eg ex en eh e [ t <sae> d <sae> ]

难度 B:

输入 t s a e d s a e e z e g e x e n e h e t s a e s a e

天 上 一只 鹅 , 地 上 一只 鹅 , 鹅 追 鹅 赶 , 鹅 上 鹅 下 , 鹅 恨  ( 鹅 / 天 上 一只 鹅 / 上 / 一只 鹅 )

注意中文字符映射功能的映射后有意义,仅对测试字符串负责,毕竟我也不知道魔王语言是什么鬼

映射表:

English char. Chinese char.
t
s
a 一只
e
d
z
g
x
n

Implement Tips

1、 将魔王的语言自右至左进栈,总是处理栈顶字符。若是开括号,则逐一 出栈,将字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列 再处理后入栈。(翻译过程中栈和队列的应用可根据算法的设计选取)。

License

ds03-magic-yyg Copyright (C) 2018 kmahyyg

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

You should have received a copy of the GNU Affero General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment