魔王语言解释(数据结构课程设计)

1.魔王语言解释

问题描述：魔王的语言精练而抽向，将他的语言按如下规则可转换成人的语言：(1) B转换为tAdA；(2) A转换为sae；(3) (qd1d2……dn)转换为qdn……qd2qd1q。输入魔王语言，输出人的语言。
例：输入数据为：

ab(sAxBq)B

输出为：

absqstsaedsaesxssaestsaedsae

用C写

/*************************************************************************
	> File Name: mo2.cpp
	> Author: kwh 
	> Mail: 
	> Created Time: 2019年12月12日 星期四 20时32分40秒
 ************************************************************************/

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

stack <char> s;
queue <char> q;
const int MAX_SIZE = 100;

int main () {
    char data;
    char s1[105];
    cin >> s1;
    for (int i = 0 ; i < strlen(s1); i++) {
        q.push (s1[i]);
    }
    while (!q.empty()) {
        if (q.front() == 'A') {
            cout << "sae";
        } else if (q.front() == 'B') {
            cout << "tsaedsae";
        } else if (q.front() == '(') {
            q.pop();
            data = q.front();
            q.pop();
            while (q.front() != ')') {
                s.push(q.front());
                q.pop();
            }
            while (!s.empty()) {
                if (s.top() == 'A') {
                    cout << data << "sae";
                } else if (s.top() == 'B') {
                    cout << data << "tsaedsae";
                } else cout << data << s.top();
                //cout << data << s.top();
                s.pop();
            }
            cout << data;
        } else if (q.front() == ')') {
            q.pop();
        } else cout << q.front();
        q.pop();
    }
    cout << endl;
    return 0;
}

面向对象封装

/*************************************************************************
	> File Name: test.cpp
	> Author: kwh 
	> Mail: 
	> Created Time: 2019年12月16日 星期一 18时04分17秒
 ************************************************************************/

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
const int MAX_SIZE = 100;

typedef int Status;
typedef char SElemType;
typedef char QElemType;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXSIZE 11

class SqStack {
    private :
        SElemType *base;
        SElemType *top;
        int stacksize;
    public :
        Status InitStack (SqStack *S);
        Status Push (SqStack *S, SElemType e);
        Status Pop (SqStack *S, SElemType &e);
};

typedef struct QNode {
    QElemType data;
    struct QNode *next;
} Qnode, *QueuePtr;

class LinkQueue {
    private :
        QueuePtr front;
        QueuePtr rear;
    public :
        Status InitQueue (LinkQueue &Q);
        Status EnQueue (LinkQueue Q, QElemType e);
        Status DeQueue (LinkQueue &Q, QElemType &e);
};

Status SqStack :: InitStack (SqStack *S) {
    base = (SElemType *) malloc (STACK_INIT_SIZE * sizeof (SElemType));
    if (!base) exit(OVERFLOW);
    top = base;
    stacksize = STACK_INIT_SIZE;
    return OK;
}

//入栈
Status SqStack :: Push (SqStack *S, SElemType e) {
    if (top - base >= stacksize) {
        base = (SElemType *) realloc (base, (stacksize + STACK_INIT_SIZE) * sizeof (SElemType));
        if (!base) exit (OVERFLOW);
        top = base + stacksize;
        stacksize += STACKINCREMENT;
    }
    *top++ = e;
    return OK;
}

//删除栈顶元素
Status SqStack :: Pop (SqStack *S, SElemType &e) {
    if (top == base) return ERROR;
    e = * --top;
    return OK;
}

//初始化队列
Status LinkQueue :: InitQueue (LinkQueue &Q) {
    front = rear = (QueuePtr) malloc (sizeof (QNode));
    if (!front) exit (OVERFLOW);
    front -> next = NULL;
    return OK;
}

//入队
Status LinkQueue :: EnQueue (LinkQueue Q, QElemType e) {

    QNode *p = (QueuePtr) malloc (sizeof (QNode));
    if (!p) exit (OVERFLOW);
    p -> data = e;
    p -> next = NULL;
    rear -> next = p;
    rear = p;
    return OK;
}

//出队
Status LinkQueue :: DeQueue (LinkQueue &Q, QElemType &e) {
    if (front == rear) return ERROR;
    QNode *p = front -> next;
    e = p -> data;
    front -> next = p -> next;
    if (rear == p) rear = front;
    free (p);
    return OK;
}

int main () {
    char data;
    char s1[MAX_SIZE];
    SqStack s;
    LinkQueue q;
    q.InitQueue (q);
    s.InitStack (&s);
    cout << "输入数据为:    ";
    cin >> s1;
    /*int i = 0;
    while ((c = getchar()) != '#') {
        s1[i] = c;
        i++;
    }*/
    for (int j = 0; j < strlen(s1); j++) {
        q.EnQueue (q, s1[j]);
    }
    cout << "输出为:        ";
    while (q.DeQueue (q, data)) {
        if (data == 'A') {
            cout << "sae";
           // printf ("sae");
        } else if (data == 'B') {
            //printf ("tsaedsae");
            cout << "tsaedsae";
        } else if (data == '(') {
            q.DeQueue (q, data);
            char temp = data;
            q.DeQueue (q, data);
            while (data != ')') {
                s.Push (&s, data);
                q.DeQueue (q, data);
            }
            while (s.Pop(&s, data)) {
                if (data == 'A') {
                    cout << temp << "sae";
                } else if (data == 'B') {
                    cout << temp << "tsaedsae";
                } else cout << temp << data;
            }
            cout << temp;
        } else if (data == ')') {
            q.DeQueue (q, data);
        } else
            cout << data;
    }
    cout << endl;
    return 0;
}

算法流程图

运行结果截图