魔王的语言

发表于 | 浏览 次

LinkQueue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
#define QElemType char

//链队列结点结构
struct LinkNode {
    QElemType data;
    LinkNode *next;
};

//带头结点的链队列结构
struct LinkQueue {
    LinkNode  *front;         //队头指针
    LinkNode  *rear;          //队尾指针
};

//构造一个空的链队列。
void InitQueue( LinkQueue &Q )
{
    Q.front = Q.rear = new LinkNode ;
    Q.front->next = NULL;
}//LinkQueue

//将链队列清空。
void ClearQueue( LinkQueue &Q )
{
    LinkNode *p;
    while ( Q.front->next != NULL )
    {
        p = Q.front->next;
        Q.front->next = p->next;
        delete p;
    }
    Q.rear = Q.front;
}

//链队列结构销毁。
LinkQueue DestroyQueue( LinkQueue &Q )
{
    ClearQueue( Q );  //成员函数Clear()的功能是释放链表中的所有元素结点
    delete Q.front;
    Q.front = Q.rear = NULL;
}

//判链队列是否为空，若为空，则返回true，否则返回false。
bool QueueEmpty( LinkQueue Q )
{
    return Q.front == Q.rear;
}

//返回链队列中元素个数。
int QueueLength( LinkQueue Q )
{
    int i = 0;
    LinkNode *p = Q.front->next;
    while ( p != NULL )
    {
        i++;
        p = p->next;
    }
    return i;
}

//取链队列队头元素的值。先决条件是队列不空。
QElemType GetHead( LinkQueue &Q )
{
    return Q.front->next->data;
}

//取链队列队尾元素的值。先决条件是队列不空。
QElemType GetLast( LinkQueue &Q )
{
    return Q.rear->data;
}

//链队列入队，插入e到队尾。
void EnQueue( LinkQueue &Q, QElemType e )
{
    LinkNode *p;
    p = new LinkNode ;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

//链队列出队。先决条件是队列不空。
bool DeQueue( LinkQueue &Q,QElemType &e )
{
    if ( QueueEmpty( Q ) )
        return false;
    LinkNode *p = Q.front->next;
    Q.front->next = p->next;
    e = p->data;
    if ( p == Q.rear )
	    Q.rear = Q.front;  //若出队后队列为空，需修改Q.rear。
    delete p;
    return true;
}

#endif

SqStack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#ifndef _SqStack_
#define _SqStack_
#define SElemType char
//顺序栈结构
struct SqStack {
    SElemType *base;     //基地址指针
    int top;            //栈顶指针
    int size;           //向量空间大小
};

//栈的初始化，分配m个结点的顺序空间，构造一个空的顺序栈
void InitSqStack( SqStack &s, int m )
{
    s.top = 0;
    s.base = new SElemType[ m ];
    s.size = m;
}

//栈销毁
void DestroySqStack( SqStack &s )
{
    delete[] s.base;
    s.top = 0;
    s.size = 0;
}

//置空栈
void ClearSqStack( SqStack &s )
{
    s.top = 0;
}

//判别栈是否为空
bool SqStackEmpty( SqStack s )
{
    return s.top == 0;
}

//求栈中元素个数
int SqStackLength( SqStack s )
{
    return s.top;
}

//取栈顶元素的值。先决条件是栈不空。
bool GetTop( SqStack s, SElemType &e )
{
    if ( ! SqStackEmpty( s ) )
    {
        e = s.base[ s.top - 1 ];
        return true;
    }
    else
        return false;
}

//入栈，若栈满，则先扩展空间。插入e到栈顶
void PushSqStack( SqStack &s, SElemType e )
{
    if ( s.top >= s.size )
    {	 //若栈满，则扩展空间。
	    SElemType *newbase;
        newbase = new SElemType[ s.size + 10 ];
        for ( int j = 0; j < s.top; j++ )
            newbase[ j ] = s.base[ j ];
        delete[] s.base;
        s.base = newbase;
	    s.size += 10;
    }
    s.base[ s.top++ ] = e;
}

//出栈,先决条件是栈非空。
bool PopSqStack( SqStack &s, SElemType &e )
{
    if ( SqStackEmpty( s ) )
        return false;
    e = s.base[ --s.top ];
    return true;
}

#endif

魔王的语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "stdio.h"
#include "SqStack.h"
#include "cstring"
#include "LinkQueue.h"

char str[100],ans[1000];
char strb[20]="tsaedsae";
char stra[20]="sae";
SqStack A;
LinkQueue B;
int main(int argc, char const *argv[]) {
    while (printf("请输入魔王的语言: (输入数字0退出程序)\n" ),scanf("%s",str )!=EOF) {
        if(str[0]=='0')
            break;
        int len=strlen(str);
        InitSqStack(A,100);
        InitQueue(B);
        for(int i=0;i<len;++i)
        {
            if(str[i]=='A')
            {
                for(int j=0;j<strlen(stra);++j)
                    PushSqStack(A,stra[j]);
            }else if (str[i]=='B') {
                for(int j=0;j<strlen(strb);++j)
                    PushSqStack(A,strb[j]);
            }else if(str[i]==')'){
                char tem;
                char rep;
                while(PopSqStack(A,tem) && tem!='(')
                {
                    EnQueue(B,tem);
                    rep=tem;
                }
                while (DeQueue(B,tem)) {
                    if(QueueLength(B)){
                        PushSqStack(A,rep);
                        PushSqStack(A,tem);
                    }else PushSqStack(A,rep);
                }
            }else{
                PushSqStack(A,str[i]);
            }
        }
        int index=0;
        while(PopSqStack(A,ans[index++])){}
        puts("翻译结果为：");
        for(int i=index-2;i>=0;--i)
            printf("%c", ans[i]);
        puts("");
    }
    return 0;
}