gost1.c

数据结构算法中的魔王语言

#include <stdio.h> /*定义头文件*/
#include <string.h>
#define MaxSize 100 /*定义最大长度*/

typedef struct stack
{
    char data[MaxSize];
    int top;
}stack;

typedef struct queue
{
    char data[MaxSize]; /*定义队列(处理括号内元素)*/
    int front;
    int rear;
}queue;
/*全局变量*/
stack S;
queue Q;
/*初始化栈和队列*/
void init()
{
    S.top=0; /*记录所有元素*/
    Q.front=0;   /*记录括号内元素*/
    Q.rear=0;
}

void push(char x) /*进栈*/
{
     S.data[S.top++]=x;
}

char pop() /*得到栈顶元素*/
{
     return(S.data[--S.top]);
}

void Inqueue(char y) /*进队列*/
{
    Q.data[Q.rear++]=y;
}

char Outqueue()   /*得到队头元素*/
{
    return(Q.data[Q.front++]);
}
/*输入魔王语言*/
Input()
{
    char str[MaxSize];
    int i;
    printf("\nEnter the gost language:");
    gets(str);/*将输入的字符串放入数组*/
    for(i=strlen(str)-1;i>=0;i--)
    {
        push(str[i]);
    }/*将输入的字符串逆序进栈，以使每次处理栈顶元素，最后一输入的顺序输出*/
}

void translate()
{
    char* RULE_B="tAdA";
    char* RULE_A="sae";
    char e,g;
    int i;
    while(S.top>0)
    {
        e=pop(); /*将栈顶元素赋给e*/
        if(e=='B')
        {
            for(i=strlen(RULE_B)-1;i>=0;i--)
            {
                push(RULE_B[i]);
            }
        }/*若e=B则使B的翻译逆序进栈*/
        else if(e=='A')
        {
            for(i=strlen(RULE_A)-1;i>=0;i--)
            {
                push(RULE_A[i]);
            }
        }/*若e=A则使A的翻译逆序进栈*/
        else if(e=='(') /*对括号进行处理*/
        {
            g=e=pop(); /*将括号内第一个元素赋给g*/
            Inqueue(g);/*第一个元素进列队*/
            while((e=pop())!=')')
            {
                Inqueue(e);
                Inqueue(g);
            }/*处理括号内的元素，每进栈一个非首元素后便使括号内首元素进栈*/
            while(Q.front!=Q.rear)
            {
                push(Outqueue()); /*将括号内的元素出队列再进栈*/
            }    
        }
        else printf("%c",e);/*打印栈顶元素（都是小写字母，即翻译后的语言）*/
    }
}

void main()
{
    Input();
    translate();
    getch();
}