【数据结构与算法】魔王语言解释（C/C++）

实践要求

1. 问题描述

有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:
形式一
$$\alpha \to {\beta }_1{\beta }_2...{\beta }_m$$
形式二
$$(\theta {\delta }_1{\delta }_2...{\delta }_n)\to \theta {\delta }_n\theta {\delta }_{n-1}....\theta {\delta }_1\theta$$

2. 基本要求

用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言解释的词汇，小写字母表示人的语言的词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人的词汇。
规则一
$$B\to tAdA$$
规则二
$$A\to sae$$

3. 测试数据

3.1 input

B(einxgz)B

3.2 output

tsaedsaeezegexeneietsaedsae

4. 实现提示

将魔王的语言自右至左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本运算。

实践报告

1. 题目分析

说明程序设计的任务，强调的是程序要做什么，此外列出各成员分工

程序设计任务：
设计一个解释魔王语言的程序将含有大写字母、小写字母、圆括号的字符串全部转化为人类语言（全部都为小写字母）。

2. 数据结构设计

说明程序用到的数据结构的定义，主程序的流程及各模块之间的层次关系

栈（用链表实现的，栈顶指针指向最上面的一个元素）

主程序流程图

各模块的层级关系

注：在此只列出有调用其他函数的函数

Main函数

InputAndCheck函数

3. 程序设计

实现概要设计中的数据类型，对主程序、模块及主要操作写出伪代码，画出函数的调用关系

数据类型

主程序操作伪代码

模块伪代码

操作伪代码

InputAndCheck

操作伪代码

字符串逆置

将一句话倒着插入栈中

将一句话正着插入栈中

4. 调试分析

遇到的问题

1. 在调用inputAndCheck函数时若输入大写字母的解释仍有大写字母将进行递归，递归传入的参数中有栈，需要注意的是不能传入一开始的栈，而是需要新开一个栈并传入也就是代码中的Stack newSta。如下：用户输入B(exingz)B -> 用户需要输入B的解释 -> 输入tAdA -> 需要用户输入A的解释 -> 输入sae。如果递归时候不传入一个新的栈，那么对A的解释将会变成tsae。
2. 在调用inputAndCheck函数的最后会将对该大写字母的解释存入test数组中，若不在最后加上 \0 则输出最终字符串时会产生输入多余的乱码的情况如（会输出tsaed潪saeezegexeneiets笅aedsae）虽然字符没错，但是会输出多余的乱码。

程序复杂度分析

$$T(n)=O(n)$$

5. 测试结果

列出测试结果，包括输入和输出

测试结果

input 1st

B(einxgz)B

output 1st

请输入B字符的解释

input 2st

tAdA

output 2st

请输入A字符的解释

input 3st

sae

output 3st

tsaedsaeezegexeneietsaedsae

6. 用户使用说明

给出主界面及主要功能界面

7. 附录

源程序文件清单:
Mowangyuyan.cpp //主程序

8. 全部代码

mowangyuyan.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAX_SIZE 100

// 定义一个结构体，用来表示栈中的节点
struct node
{
    char val;
    node *next;
};

// 定义一个栈类
class Stack
{
private:
    // 栈顶指针
    node *top_ptr = nullptr;

public:
    // 判断栈是否为空
    bool isEmpty()
    {
        return top_ptr == nullptr ? true : false;
    }
    // 获取栈顶元素
    char top()
    {
        return top_ptr->val;
    }
    // 入栈操作
    void push(char c)
    {
        node *new_node = new node{c, top_ptr};
        top_ptr = new_node;
    }
    // 弹出栈顶元素
    bool pop()
    {
        if (isEmpty())
            return false;
        node *to_be_deleted = top_ptr;
        top_ptr = top_ptr->next;
        delete to_be_deleted;
        return true;
    }
    // 置空栈
    void clear()
    {
        while (top_ptr)
        {
            node *tmp = top_ptr;
            top_ptr = top_ptr->next;
            delete tmp;
        }
    }
    // 析构函数
    ~Stack()
    {
        clear();
    }
};
// 将字符串逆置
void reverseStr(char str[], int length)
{
    int start = 0;
    int end = length - 1;
    while (start < end)
    {
        swap(str[start], str[end]);
        start++;
        end--;
    }
}
// 将一条语句倒着放入栈中
void invert(Stack &sta, char setence[])
{
    // 一句话的长度
    int len = strlen(setence) / sizeof(char);
    for (int i = len - 1; i >= 0; --i)
    {
        sta.push(setence[i]);
    }
}
// 将一句话正着放入栈中
void reverseInvert(Stack &sta, char setence[])
{
    // 一句话的长度
    int len = strlen(setence) / sizeof(char);
    for (int i = 0; i <= len - 1; ++i)
    {
        sta.push(setence[i]);
    }
}

// 检查输入的字符是否全为小写字符 ch为输入的字符，index为其字符的ASCII码 - A的ASCII的值, text为预处理后的各大写字母的表示
void inputAndCheck(Stack &sta, char ch, int index, char test[26][MAX_SIZE])
{
    char supperVoca[MAX_SIZE]; // 存放用户输入该大写字母的表示
    int vocaVal;               // 输入解释字符的ASCII码
    char final[MAX_SIZE];      // 最终的解释
    printf("请输入%c字符的解释", ch);
    scanf("%s", supperVoca);
    for (int i = 0; i < strlen(supperVoca) / sizeof(char); i++) // 挨个检查输入的解释是否为小写字母
    {
        vocaVal = supperVoca[i];
        if (isupper(vocaVal) && test[vocaVal - 'A'][0] == '\0') // 如果输入的是大写字母且该大写字母并无解释
        {
            if (vocaVal - 'A' != index) // 检查是否为已经处理过的字母，避免死循环
            {
                Stack newSta;                                              // 创建一个空栈(易漏)
                inputAndCheck(newSta, supperVoca[i], vocaVal - 'A', test); // 递归
            }
        }
        if (isupper(vocaVal) && test[vocaVal - 'A'][0] != '\0') // 如果输入的是大写字母且该大写字母有相应的解释
        {
            reverseInvert(sta, test[vocaVal - 'A']); // 将该大写字母的解释正着插入栈中
        }
        else
            sta.push(supperVoca[i]); // 如果是小写字母则直接插入栈中
    }
    int i = 0; // 共有多少个字符
    while (!sta.isEmpty())
    {
        char tmp = sta.top();
        sta.pop();
        final[i] = tmp;
        i++;
    }
    reverseStr(final, i);
    int j = 0;
    while (j < i)
    {
        test[index][j] = final[j];
        j++;
    }
    test[index][j] = '\0'; // 在每个大写字母的最终解释后加个\0
}
int main()
{
    // test
    char test[26][MAX_SIZE];        // 存放26个大写英文字母的所对应的小写字母解释
    char language[MAX_SIZE];        // 一开始的魔王语言
    char inBrackets[MAX_SIZE];      // 括号内的字符
    char translatedInBra[MAX_SIZE]; // 转化括号内的字符
    char translation[MAX_SIZE];     // 最终解释的字符
    bool flag = false;              // 是否在括号内的标志
    Stack translatedLanguage;       // 经过大小写转换后的栈
    Stack finalInterp;              // 每个大写字母最终解释的栈
    for (int i = 0; i < 26; ++i)    // 初始化
    {
        test[i][0] = '\0';
    }
    scanf("%s", language);                            // 输入魔王语言
    int langLength = strlen(language) / sizeof(char); // 求出输入字符的长度
    for (int i = 0; i < langLength; i++)
    {
        int Char = language[i]; // 字符的ASCII码值
        if (isupper(Char))
        {
            if (test[Char - 'A'][0] == '\0')
            {
                // 输入并检查是否含有大写字幕
                inputAndCheck(finalInterp, language[i], Char - 'A', test);
            }
        }
    }
    reverseInvert(translatedLanguage, language);
    int i = 0;
    int j = 0;
    while (!translatedLanguage.isEmpty())
    {
        char tmp = translatedLanguage.top();
        translatedLanguage.pop();
        if (isupper(tmp))
        {
            reverseInvert(translatedLanguage, test[tmp - 'A']);
        }
        else if (tmp == ')')
        {
            flag = true;
        }
        else if (tmp == '(')
        {
            flag = false;
            int inBracketsLength = strlen(inBrackets) / sizeof(char);
            int counter1 = 0;
            int counter2 = 0;
            while (counter1 != inBracketsLength)
            {
                translatedInBra[counter2] = inBrackets[inBracketsLength - 1];
                if (counter1 != (inBracketsLength - 1))
                {
                    translatedInBra[counter2 + 1] = inBrackets[counter1];
                }
                counter1 = counter1 + 1;
                counter2 = counter2 + 2;
            }
            reverseInvert(translatedLanguage, translatedInBra);
        }
        else
        {
            if (flag)
            {
                inBrackets[i] = tmp;
                i = i + 1;
            }
            if (!flag)
            {
                translation[j] = tmp;
                j++;
            }
        }
    }
    reverseStr(translation, j);
    for (int k = 0; k < j; k++)
    {
        printf("%c", translation[k]);
    }
    return 0;
}

结束语

  因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！文章来源地址https://www.toymoban.com/news/detail-734504.html

到了这里，关于【数据结构与算法】魔王语言解释（C/C++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！