源代码仓库在下方卡片↓

1 引言

该课程设计旨在实现一套能够完全随机地生成带括号的四则运算表达式的算术练习器以供学生进行算术练习，在这个基础上，随时可以退出，并保存历史分数，能回顾历史，同时在完成练习后给出与历史成绩比较后的评价。这就围绕着随机算术表达式的生成到逆波兰表达式(RPN)的转换，最终对RPN进行解析并计算结果这三个步骤来完成。

该课程设计在Windows 11 23H2系统下，使用Clion 2023.1.5 IDE与MinGw编译环境开发。

2 系统设计

以一个后缀算式为例，9 2 3 + – 10 2 / -，遇到数字将会一直入栈，直到遇到了四则运算符号（二元运算符）后进行两个数的出栈，计算出结果后再入栈，一直循环直到最后计算出结果，检查是否与用户输入的结果相符，由于要求整个步骤进行随机化并且自动生成，结果不可被确定类型。此外，我们知道，由于IEEE 754浮点数标准，对最终运算结果需要进行一些精度上的宽容，因而这里对标准栈加以改造为多态顺序栈。安排符号与括号的位置同样需要加以考虑，在固定的位置安排符号固然可以降低难度，但是这会让生成的算式不够随机。经过和同学的热烈交流，分析出了二栈归一队列（随机生成数值和运算符，并使用泛型栈来存储他们，但是不能确定弹出栈进行运算的时机），随后又想到了三栈归一队列（数值栈，符号栈和储存顺序的指针栈，这样解决了逆波兰表达的运算顺序问题），但是还不够好，由于最近写的Rust导致对所有权和生命周期之类印象深刻，最后思维打开到先递归深度生成人类可读的表达式（String），并将该表达式转换为逆波兰表达式（String），随后遍历入栈计算出表达式结果。

一共定义了，main.cpp, HandleRequesst.cpp, GenerateArithmeticExpression.cpp, ConvertToRPN.cpp, CheckResult.cpp, HandleHistory.cpp，两种数据类型的栈以及上述相应的头文件。

3 系统实现

一个典型运行的流程图可以参照下方图片的箭头步骤进行。(段落前的序号代表流程图上的步骤序号)

这个实现的说明按照GitHub仓库中第e401165e567fec2c249d23507ab4f28d4fc91249版本为准。（除了HandleRequest.cpp中的一处逻辑错误修正）

1.首先，用户输入功能序号来进行答题，主函数便会将读入的char转换为int并传递给handleQuery()函数，handleQuery()函数首先会查找用户的最好答题记录，并暂存，之后匹配用户选择的功能，在我们这里选择了随机数量的题目，因此函数还会生成一个随机数作为generateQuest()的questNum形参，这就是随机生成题目的数量。

关于随机数的生成，在C++11标准后更推荐使用随机模板类来代替先前c标准中的随机函数，因此在这里使用了c++ random库。可以看到，在main.cpp文件中定义了全局变量default_random_engine engine，这将被其他几个函数使用来生成可靠的随机数。

实例化default_random_engine类并且不附带任何参数所生成的随机数引擎会使用相同的种子，因此结果是可预测的。在Windows 11的g++编译器上，clion解析default_random_engine使用的是linear_congruential_engine，为线性同余算法(typedef linear_congruential_engine<uint_fast32_t, 16807UL, 0UL, 2147483647UL> default_random_engine)。

random_device类可以提供以计算机系统的熵来生成的随机数，因此我们可以认为他生成的随机数是真随机数。将这个随机数作为随机引擎的种子，相较于time(NULL)，可以避免在循环中出现重复结果（循环过快导致以秒为单位的时间种子重复）。

2&3.在generateQuest()函数中，也会生成一个随机数，这个随机数将被作为调用递归函数的深度次数，接下来就进行生成随机算术表达式的步骤，调用generateRandomExpression()函数，可以注意到在调用之前原函数还会对深度次数进行判断，如果深度次数不为2，便会传递为1的sign参数，该检查是为了减少随机生成的重复括号，sign参数为1时，函数在当前深度进行递归时就不进行向表达式随机加入括号的操作。

 4.在generateRandomExpression()函数中便负责递归地生成随机数学表达式，数字，运算符和括号全都被随机地生成， 接着拼接到字符串中，返回给调用函数handleQuery()，一开始想的比较复杂，不过之后调试了很多次，使用递归和字符串拼接以及一些标志变量最终实现了。

 5.随后，函数接收到字符串，输出给用户，等待用户输入结果（可以考虑在这里做并发，在等待的同时先计算出结果），在处理输入的时候使用了stl和try-catch来实现同时处理浮点数与整型的输入，本来打算使用泛型处理的，但实际上，如果编译器无法确定泛型的类型（比如用户输入这种情况，是不可预知的），便无法通过编译，输入后把数学表达式字符串传递给convertToRPN()函数，该函数负责将普通四则运算表达式转换为逆波兰表达式，用于后续被程序计算出结果，类似于后端中的中间件。这里使用了for-each语法糖，遍历字符串使用char，遇到数字直接拼接给字符串，如果是符号或空格就在进行一次判断，比如是二元运算发，存放符号的栈非空并且该遍历字符优先级低于栈顶字符，便将该运算符拼接到字符串中，同时弹出一个栈中符号并更新条件字符。同时还着重了该rpn字符串的空格处理，否则会对后续计算结果造成较大困扰。在完成这个函数上也花了较多时间，不能使用类和对象导致自己实现的栈一种数据类型就得写两份文件。C++的泛型不如rust那样好用，泛型栈如果用c语言的void *指针来实现是可以的，但是也比较麻烦，不过有朋友指出可以再在栈中定义一个联合体和标志变量来实现泛型存放的数据类型，确实可以实现多种数据类型的栈，不过当时已经完成重写工作了，就没有再进行重写。

 6.在返回转换的逆波兰表达式后，再将该表达式传递给calculateResult()函数，这个相对简单，依靠先前逆波兰表达式的转换，可以作为后缀算式来计算，这里使用到了double类型的栈来存放数字，至于返回值也是double还是因为先前泛型的问题，统一作为浮点数来计算了。

 7.返回生成表达式的结果后，再传递给<T>bool checkResult(T result, double calculatedResult)泛型函数，泛型可以解决用户输入的是浮点还是整型的问题了，使用std::is_same<T,typename>::value可以判断T的类型具体为什么类型。如果是浮点数，由于IEEE 754浮点数的特性，函数将把系统计算结果先进行保留两位小数的四舍五入后再和用户输入结果相减，判断绝对值小于0.00001便判定为正确结果，C++没有java好用的高精度运算库，因此只能这样处理来验证浮点数结果了。

 8.checkResult()函数返回结果后，便会进行判断，如果错误的话还会给予用户一次机会，goto到retry:标签在进行一次判断。正确的话返回true给handleQuery()函数，他会调用saveScore()函数写入到成绩记录文件，错误的话返回false，不写入，并开始下一道题。

9&10.当所有题目答题完成后，会检查与上次最好成绩的结果并给予用户本次答题评价，如果是第一次答题则不显示评价，之后调用bool saveScore()函数来写入本次答题的成绩，到这里，一次答题的步骤便完成了。

此外，负责存储答题情况的结构体可以把正确题数改为正确率占比，这样反映的比较情况更加客观一点。

以下为程序部分源代码，由于模块分层比较多，详情可以参照一起打包的完整程序源代码。

// main.cpp

// Created by Shanwer on 2023/10/29.

//

#include <iostream>

#include <random>

#include "HandleRequest.h"

using namespace std;

random_device rd;

default_random_engine engine{rd()};

int main(){

    cout << "欢迎使用四则运算练习器，请选择要使用的功能" <<endl;

    cout << "输入数字(1,2,3...)来选择功能" << endl;

    cout << "1. 选择指定数量的题目" << endl;

    cout << "2. 选择随机数量的题目(20道以内)" << endl;

    cout << "3. 查看历史最高分数" << endl;

    cout << "4. 查看全部历史成绩" << endl;

    cout << "9. 退出(或输入其他数字)" << endl;

    cout << "PS:生成的算式各数字均在50以内，如果结果为小数，保留两位，计算错误有一次重试机会，回答问题输入wq的时候可以直接保存成绩并退出" << endl;

    cout << "PPS:问题未全部完成就退出会把剩下的题目视作答错" <<endl;

    cout << "请输入数字:";

    handleQuery(cin.get()-'0');//char类型数字 - char类型数字算出int

}

// HandleRequest.cpp

// Created by Shanwer on 2023/10/29.

//

#include <iostream>

#include <string>

#include <random>

#include "GenerateArithmeticExpression.h"

#include "CheckResult.cpp"

#include "ConvertToRPN.h"

#include "HandleHistory.h"

using namespace std;

extern random_device rd;

extern default_random_engine engine;

uniform_int_distribution<unsigned> expressionDepth(1,3);

uniform_int_distribution<unsigned> randomQuest(1,20);

bool generateQuest(int correctTimes,unsigned int questNum) {

    string rawString;

    //handledString;

    unsigned int randomDepth = expressionDepth(engine);

    if (randomDepth == 1 || randomDepth == 3) {

        rawString = generateRandomExpression(randomDepth, 1);

    } else {

        rawString = generateRandomExpression(randomDepth, 0);

    }

    //上述检查都是为了减少随机生成的重复括号，sign参数为1时，函数在当前深度进行递归时就不进行向表达式随机加入括号的操作

    //handledString = rawString;

    cout << "请计算:" + rawString << endl;

#ifndef NDEBUG

    cout << "生成的RPN:" + convertToRPN(handledString) << endl;

#endif

    int retryTime = 1;

    double calculatedResult = calculateResult(convertToRPN(rawString));

    retry:

    string inputResult;

    cin >> inputResult;

    try {

        double doubleResult = stod(inputResult);//如果不为浮点就捕获异常转为整型

        if (checkResult<double>(doubleResult, calculatedResult)) {

            cout << "结果正确" << endl;

            return true;

        } else if (retryTime != 0) {

            cout << "结果错误，再试一次吧" << endl;

            retryTime = 0;

            goto retry;

        } else {

            cout << "结果错误" << endl;

            return false;

        }

    } catch (const invalid_argument &) {

        try {

            int intResult = stoi(inputResult);

            if (checkResult<int>(intResult, calculatedResult)) {

                cout << "结果正确" << endl;

                return true;

            } else if (retryTime != 0) {

                cout << "结果错误，再试一次吧" << endl;

                retryTime = 0;

                goto retry;

            }else {

                cout << "结果错误" << endl;

                return false;

            }

        } catch (const invalid_argument &) {

            if(inputResult == "wq"){

                cout << "保存并退出中...";

                saveScore(correctTimes,questNum);

                exit(0);

            }else{

                cout << "输入内容错误，只能输入数字和wq指令哦" << endl;

                goto retry;

            }

        }

    }

}

void handleQuery(int input){

    unsigned int questNum;

    int correctTimes = 0;

    int highest = findHighest();

    switch(input){

        case 1:

            cout << "输入想要的题目数量:";

            cin >> questNum;

            for(unsigned int i = questNum; i > 0; i --){

                if(generateQuest(correctTimes,questNum)){

                    correctTimes ++;

                }

            }

            saveScore(correctTimes,questNum);

            if(highest <= correctTimes){

                cout << "你上次最多做出了:"  << highest << "道题！" << endl;

                cout << "做的比上次还多，真不错，再接再厉!" << endl;

            }else if(highest == -1){

                break;

            }else{

                cout << "你上次最多做出了:"  << highest << "道题！" << endl;

                cout << "做的没有上次多，但也没关系，下次加油!" << endl;

            }

            break;

        case 2:

            questNum = randomQuest(engine);

            cout << "随机生成了:" << questNum << "道题目" << endl;

            for(unsigned int i = questNum; i > 0; i --) {

                if(generateQuest(correctTimes,questNum)){

                    correctTimes ++;

                }

            }

            saveScore(correctTimes,questNum);

            if(highest <= correctTimes){

                cout << "你上次最多做出了:"  << highest << "道题！" << endl;

                cout << "做的比上次还多，真不错，再接再厉!" << endl;

            }else if(highest == -1){

                break;

            }else{

                cout << "你上次最多做出了:"  << highest << "道题！" << endl;

                cout << "做的没有上次多，但也没关系，下次加油!" << endl;

            }

            break;

        case 3:

            if(highest==-1){

                cout<< "你还没写呢，先去写几道题存个记录吧！"<<endl;

            }else {

                cout << "你的最好成绩一共做出了:" << highest << "道题！" << endl;

            }

            break;

        case 4:

            traverseScoreFile();

            break;

        default:

        case 9:

            cout << "退出";

            break;

    }

}

// GenerateArithmeticExpression.cpp

// Created by Shanwer on 2023/10/29.

//

#include <iostream>

#include <random>

using namespace std;

extern random_device rd;

extern default_random_engine engine;

//normal_distribution<> randomDouble(25,10); //正态分布模板类，均值为25，标准差为10，生成值默认为double

uniform_int_distribution<unsigned > randomNum(1,50);

// 生成随机整数

int generateRandomNumber(int min, int max) {

    return min + engine() % (max - min + 1);

}

// 生成随机运算符

char generateRandomOperator() {

    char operators[] = {'+', '-', '*', '/'};

    unsigned int index = engine() % 4;

    return operators[index];

}

// 生成随机数学表达式

string generateRandomExpression(int depth, int sign) {

    if (depth == 0) {

        // 生成随机整数作为操作数

        return to_string(randomNum(engine));

    } else {

        string expression;

        int generateParentheses = generateRandomNumber(0, 1); // 随机生成括号

        char op = generateRandomOperator(); // 随机生成运算符

        // 递归生成左右两个子表达式

        string left = generateRandomExpression(depth - 1, 0);

        string right = generateRandomExpression(depth - 1, 0);

        if (sign == 1){

            generateParentheses = 0;

        }

        if (generateParentheses > 0) {

            expression += "(";

        }

        expression += left;

        expression += " ";

        expression += op;

        expression += " ";

        expression += right;

        if (generateParentheses > 0) {

            expression += ")";

        }

        return expression;

    }

}

4 小结

对于结果评价的实现，还可将单纯答题正确数的绝对值比较改为按比例与平均时间的综合评价，同时也可加入配置文件来设定递归深度（决定算式复杂度），递归随机值概率的分布情况，随机生成题目的题量等等，当然这是可以改进的地方，不是本篇课设主要解决的问题。

一开始我错误的理解了题目，专注在对于预生成的算式进行正则处理后入栈计算结果，实际上题目要求整个算式都要随机生成的，这样对难度又是一个档次的提升。

此外，各个语言的泛型实现也有很大区别，Java这一类语言可以算伪泛型，C#这一类语言可以算真泛型，Go的泛型是类型组合，标准C没有泛型，因此为了实现目的所需要的方法有很大的不同之处，最近学习Rust语言的时候认为学习起来相对简单的C++可以更简单的实现泛型，反而踩了许多坑。总而言之，编译器一般不会做不确定的承诺，除非他认为程序员什么都知道(C++的指针),否则就把程序员当白痴(所有权与生命周期，unsafe)。

数据结构和算法作为程序员的基本功也确实很重要，尽管大部分的crud工作并不需要多复杂的算法，但是熟练使用一些高级数据结构和算法也是必要的，除此之外，深入低级语言与操作系统的各种交互实现，脱离高级语言抽象的调包也有助于理解这些抽象用法的底层实现。

参考文献

（其实并没有参考）

[1] 郑致力.算术表达式解析引擎的设计及实现【D】.北京邮电大学,2012(03).