spn-Jimmy 2003-12-23 09:53
大家好！求救一道题目（栈和队列的应用）
问题描述：
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听的懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
1。α->β1β2……βm
2.(θδ1δ2……δn)->θδnδn-1……θδ1θ
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听的懂的话。
基本要求：
用下述两条具体规则和上述规则形式2实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
1 B->tAdA
2 A->sae
希望大家帮忙，谢谢啊。 [img]http://bbs.tongji.net/images/smiles/laugh.gif[/img]
gavin_zw 2008-11-7 12:04
[测试数据]
B(einxgz)B
解释成tsaedsaeezegexeneietsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一个鹅地上一个鹅鹅追鹅赶下鹅蛋恨鹅天上一人鹅地上一个鹅“。
t d s a e z g x n I
天 地 上 一个 鹅 追 赶 下 蛋 恨
[实现提示]
将魔王语言自右到左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本运算。
在网上找到了题目的提示，规则2的描述和我的理解有点出入。。。
哦，编译原理。。。最右推导。。。
以测试数据为例，先将B入栈，因为替换规则B->tAdA，将B pop出去并替换成tAdA的形式，然后将A入栈，按照A->sae规则替换，然后顺序将sae入栈。。。
过程如 B(einxgz)B -> B(einxgz)tAdA
-> B(einxgz)tAdsae
-> B(einxgz)tsaedsae
-> Bezegexeneietsaedsae
-> tAdAezegexeneietsaedsae
-> tAdsaeezegexeneietsaedsae
-> tsaedsaeezegexeneietsaedsae
出入栈的情况为
B入栈->B出栈->A入栈->A出栈->e入栈->a入栈->s入栈->d入栈->A入栈->A出栈->e入栈->a入栈->s入栈->t入栈。。。。
(exingz)根据抽象规则2解析，)入栈->z入栈->g入栈->n入栈->i入栈->x入栈->e入栈->(入栈，用队列将序列倒置处理再将结果入栈，剩余的与前面一样
实现就交给taro桑吧，给你个机会赚积荤。
[[i] 本帖最后由 gavin_zw 于 2008-11-7 12:06 编辑 [/i]]
taro 2008-11-9 09:13
被2#召唤来了，还是忍不住要说你这个wsn一句，居然叫我实现这个bt的东西，还好魔王只会说两种话，否则我high死了，实现跟分析的难度明显不是一个等级的嘛 :devil_smile:
按照2#的分析做的，如理解有误，请抽2# :laugh:
顺便帮我测一下，早上头昏脑涨的 :dozingoff:
PS: str[ i ]里的[ i ]全被吃掉了，禁用掉又太丑，无奈之下还是用ii代替i作为循环变量好了 :angry.gif:
翻译过程如下：
1、输入要翻译的字符串，取名next
2、下一个字符(最右边的字符)入栈
3、若栈顶等于‘)’或者是小写字母，什么都不做
若栈顶等于‘(’，一直pop直到遇到')'，把括号之间的东西做(θδ1δ2……δn)->θδnθδn-1θ……θδ1θ变换，并把结果加到next后面
若栈顶等于‘B’，pop ‘B'，把tAdA加到next后面
若栈顶等于‘A’，pop ‘A'，把sae加到next后面
4、重复step 2直到next里的所有字符都进栈了
5、依次弹出栈内的东西，赋值给result，结束[code]#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 100
typedef struct StackNode
{
char entry;
struct StackNode * next;
}StackNode, *PNode;
void pop(PNode * topNode)
{
PNode temp = *topNode;
*topNode = (*topNode)->next;
free(temp);
}
void push(PNode * topNode, char c)
{
PNode temp = (PNode)malloc(sizeof(StackNode));
temp->entry = c;
temp->next = *topNode;
*topNode = temp;
}
// to do "(θδ1δ2……δn)->θδnθδn-1θ……θδ1θ"
void reverse(char * dest, const char * src, int len)
{
int ii, j;
dest[0] = src[0]; // insert first θ
for(ii = len - 1, j = 1; ii >= 1; ii--)
{
dest[j++] = src[ii]; // copy δn-ii+1
dest[j++] = src[0]; // insert θ
}
}
// returns negative number when syntax error or length of result string
int checkValid(const char * str)
{
int ii, j = 1, result = 0, len = strlen(str);
for(ii = 0; ii < len; ii++)
{
if(str[ii] >= 'a' && str[ii] <= 'z')
{
result += j;
}
else if(str[ii] == 'A')
{
result += 3 * j; // A->sae;
}
else if(str[ii] == 'B')
{
result += 8 * j; // B->tAdA->tsaedsae;
}
else if(str[ii] == '(')
{
j *= 2;
}
else if(str[ii] == ')')
{
if(j == 1 || str[ii - 1] == '(') // brackets not match
return -2;
else
{
j /= 2;
result -= j;
}
}
else
{
return -1; // invalid char
}
}
return result;
}
char * translate(const char * str) // returns NULL if syntax error
{
PNode top = NULL;
int ii, j, k, len = strlen(str), resultLen = checkValid(str);
char * result = NULL, * temp = NULL;
if(resultLen < 0)return NULL; // input string is not valid
result = (char *)malloc(sizeof(char) * (resultLen + 1));
temp = (char *)malloc(sizeof(char) * ((len > resultLen ? len : resultLen) + 1));
strcpy(temp, str);
for(ii = len - 1; ii >= 0; ii--)
{
push(&top, temp[ii]);
switch(top->entry)
{
case ')': // do nothing
break;
case '(': // pop until top->entry equals ')' then reverse
k = 0;
pop(&top); // pop '('
while(top->entry != ')')
{
result[k++] = top->entry;
pop(&top);
}
reverse(temp + ii, result, k);
ii += 2 * k - 1;
pop(&top); // pop ')'
break;
case 'A': // A->sae;
pop(&top);
strcpy(&temp[ii], "sae");
ii += 3;
break;
case 'B': // B->tAdA;
pop(&top);
strcpy(&temp[ii], "tAdA");
ii += 4;
break;
default:
break;
}
}
j = 0;
while(top != NULL) // pop all nodes in stack
{
result[j++] = top->entry;
pop(&top);
}
free(temp);
result[resultLen] = '\0';
return result;
}
void main()
{
char str[MAX_LENGTH];
char * result = NULL;
printf("Please input the string to be translated: (less than 100 chars)\n");
gets(str);
//printf("Length of result: %d\n",checkValid(str));
result = translate(str);
if(result == NULL)
printf("Syntax Error!\n",result);
else
{
printf("Result: %s\n",result);
free(result);
}
}[/code]
[[i] 本帖最后由 taro 于 2008-11-9 09:30 编辑 [/i]]
taro 2008-11-9 10:57
[quote]原帖由 [i]gavin_zw[/i] 于 2008-11-9 10:45 发表 [url=http://bbs.tongji.net/redirect.php?goto=findpost&pid=8142063&ptid=101219][img]http://bbs.tongji.net/images/common/back.gif[/img][/url]
你8G棒子买好了伐 [/quote]
没有，侬居然在这里水 =。=