作业 20180925-6 四则运算试题生成

作业要求:【https://edu.cnblogs.com/campus/nenu/2018fall/homework/2148】

作业地址：【https://git.coding.net/zhangjy982/ArithMetic.git】

要求1：

一、重点和难点

---

1.功能1的重点和难点

(1).随机出题

题目要求出题随机，其中包括操作数随机和操作符随机，随机产生这两项之后再组成用于计算的式子。下面是我取随机操作数和操作符的代码：

public List<string[]> getRandomNum()                 // 获取4个1-20之间的随机操作数
        {
            List<string[]> randomNums = new List<string[]>();
            string[] randomFractions = new string[4];// 保持分数的形式方便展示
            string[] randomRealNum = new string[4];  // 把分数转化为小数方便计算（功能4中用得到）
            
            string number1 = "";
            string number2 = "";
            for (int i = 0; i < 4; i++)
            {
                int flag = rm.Next(1, 11);
                switch (flag % 2)
                {
                    case 0:
                        number1 = rm.Next(1, 20).ToString();
                        randomFractions[i] = number1;
                        randomRealNum[i] = number1;
                        break;
                    case 1:
                        number1 = rm.Next(1, 20).ToString();
                        number2 = rm.Next(1, 20).ToString();
                        randomFractions[i] = number1 + "/" + number2;
                        randomRealNum[i] = (Convert.ToDecimal(number1)/Convert.ToDecimal(number2)).ToString();
                        break;
                }
            }
            randomNums.Add(randomFractions);
            randomNums.Add(randomRealNum);
            return randomNums;
        }

public string[] getRandomOperator()         // 获取3个随机操作符符
        {
            string[] operators = new string[4];
            string[] randomOperators = new string[3];
            operators[0] = "+";
            operators[1] = "-";
            operators[2] = "*";
            operators[3] = "/";
            for (int i = 0; i < 3; i++)
            {
                randomOperators[i] = operators[rm.Next(0, 4)];
            }
            return randomOperators;
        }

功能1的运行截图：（写博客已完成4个功能，所以这里显示有分数表示，因为分数的“/“号和运算符“/”除号容易使公式不明晰，所以对象之间加了空格）

2.功能1的编程收获

因为测试和熟练度的问题，和结对伙伴商量之后从Python语言转到了C#，对C#比Python要熟悉很多，所以刚开始做功能1比较得心应手，之前用Python的时候少了很多面向对象的思想和方法，把功能都写在了一起。现在开始结对编程对代码的可读性要求非常高，因此在功能1中就开始注意一些代码的复用和重用，把功能尽量细化，每一个小功能对应一个方法，类似的几个方法写成一个类，尽量做到高内聚、低耦合，对以后程序的进一步开发也有很多好处；

3.功能2的重点和难点

(1).生成括号的位置

因为括号的生成位置不固定，一个式子中可能有1个或2个括号，这些括号的位置也各不相同，但是操作数只有4个，我们讨论之后决定把这些括号的可能位置枚举出来，情况总共有10种，我们使用switch case将这些情况都枚举出来，随机生成1~100之内的整数，然后用整数%10可以得到10个case，进而完成括号位置的生成；

(2).括号的匹配及运算的优先级

除了添加括号过程之外，括号的引入主要是改变了方程的算术优先级，看到这我首先想到的是数据结构中栈的应用这块，所以我们马上找到了数据结构的书和王道，又参考了网上博客的内容，制定了解决方案：先把运算符的优先级制定好，然后把中缀表达式转化为后缀表达式，也就是逆波兰的相关内容，最后通过栈的性质依次去除操作数和操作符进行运算并输出结果的过程，代码如下：

定义运算符优先级：

public static int GetOperationLevel(string c)      // 定义运算符优先级
        {
            switch (c)
            {
                case "+": return 1;
                case "-": return 1;
                case "*": return 2;
                case "/": return 2;
                case "#": return -1;
                case "(": return -1;
                case ")": return -1;
                default: return 0;
            }
        }

转化为后缀表达式：

public Stack<string> getReversePolish(string equation)
        {
            //equation = "(1+2)*3";
            Stack<string> opStack = new Stack<string>();        // 定义运算符栈
            opStack.Push("#");
            Stack<string> numStack = new Stack<string>();       // 定义操作数栈
            for(int i = 0; i < equation.Length;)
            {
                int opNum = GetOperationLevel(equation[i].ToString());
                if (opNum == 0)
                {
                    int index = GetCompleteValue(equation.Substring(i, equation.Length - i));
                    numStack.Push(equation.Substring(i, index));
                    i = (i + index);
                }
                else
                {
                    if (equation[i] == '(')
                    {
                        opStack.Push(equation[i].ToString());
                    }
                    else if (equation[i] == ')')
                    {
                        MoveOperator(opStack, numStack);
                    }
                    else
                    {
                        if (opStack.Peek() == "(")
                        {
                            opStack.Push(equation[i].ToString());
                        }
                        else
                        {
                            JudgeOperator(opStack, numStack, equation[i].ToString());
                        }
                    }
                    i++;
                }
            }
            if (opStack.Count != 0)
            {
                while (opStack.Count != 0 && opStack.Peek() != "#")
                {
                    numStack.Push(opStack.Pop());
                }
            }
            return numStack;
        }

计算表达式的值：

 public Stack<string> getRpnEquation(Stack<string> numStack)
 {
     Stack<string> rpnEquation = new Stack<string>();     // 逆波兰
     foreach (string s in numStack)
     {
          rpnEquation.Push(s);
     }
     return rpnEquation;
}

public string CalcRPNFormula(Stack<string> rpnFormula)
{
    string result = "";
    Stack<string> resultStack = new Stack<string>();
    foreach (string s in rpnFormula)
    {
        int num = GetOperationLevel(s);
        if (num == 0)
        {
             resultStack.Push(s);
        }
        else
        {
              CalcResult(resultStack, s);
        }
     }
      result = resultStack.Pop();
            //Console.WriteLine(result);
      return result;
}

功能2运行截图：

4.功能2的编程收获

 功能2主要是逆波兰的使用和栈的使用，最明显的收获当然是对栈的理解加深了很多，对C#中栈的使用更加熟悉，以后遇到问题用栈解决成为了一个非常值得尝试的选择；其次就是更加加深了对数据结构这门专业基础课的认识，越来越觉得数据结构在编程中的重要作用，这次用到了栈，下次可能还会遇到队列等数据结构，所以以后要更加强对各种数据结构的了解，争取用语言去实现各种数据结构和算法，伪代码虽然看起来非常便捷，但是对于编程能力非常一般的我来说伪代码到语言实现还是有一定的距离的，所以要更加加强算法代码实现这一块内容；

5.功能3的重点和难点

(1).命令行参数

功能3再次出现了命令行参数，经过了之前的训练，这一块已经不是难点，但是还是此功能的一个重点，C#和Python在命令行参数之中的区别在于Python是把程序的名字当做第一个命令行参数，C#是传进去的是什么那么使用中就是什么，没有多余的一项命令行参数；

(2).限定题目数量，区分命令行参数是否为正整数

第二个命令行参数可能是字符串或者小数等，这样就没办法完成限定题目数量的问题，所以首先要判断第二个命令行参数是否为正整数，我们采用的是正则表达式的方式，正则代码如下：

static bool isNumeric(string value)                    // 判断第二个命令行参数是否为正整数
{
   return Regex.IsMatch(value, @"^[+]?d+$");      
4 }

(3).精美打印输出

因为括号数量的不一样，所以生成的方程式长短不一，我们采用的方法是通过String.PadRight(length,string)把方程后面补上空格组成长短一致的字符串；另外功能还要求输出到txt文件中，这里用到了C#的输入输出流，使用StreamWriter对象对文件进行写入操作，由于每次写入会覆盖原来的文件，所以我们先把所有的题目都生成保存在List<string>中，最后统一打印输出，打印代码如下：

public void produceFiles(string filename,List<string> equations)       // 传入参数为文件名和写入内容
{
    StreamWriter streamWriter = new StreamWriter(filename, false, Encoding.Default);
    for(int i = 0; i < equations.Count;i++)                           // 按条将题目打印到文件
    {
        streamWriter.WriteLine(equations[i]);
    }
    streamWriter.Flush();
    streamWriter.Close();
 }

(4).去除重复

这块我感觉是整个项目中最难处理的一部分，在网上搜了很多方法，比如树的最小表示法区分同构的树等等，我们尝试了很多但是没有达到预想的效果，所以最后我们两个人经过讨论决定使用这样一种判断：如果两条题目的结果相同、操作数和操作符相同（顺序可能不同，经过排序后比较是否相同），虽然没有非常精确地算法，但是输出的同样是没有重复的题目，同样完成了功能，因为结果不同的题目构成肯定不相同。缺憾就是生成过程中会多丢弃几个题目，但是对整体影响非常小，我们也对自己的想法比较满意；

功能3的运行效果截图：

控制台的输出效果：

生成的文件内容：

6.功能3的编程收获

功能3最大的难点在于去重，我们最后也没有找到最优解，但是我们经过讨论和分析制定了一个不是最优解但是相差不大的解决方案，在同等情况下，我可能实现最优解需要用8个小时，但是我的非最优解只需要花费我3个小时的时间，而在性能上非最优解比最优解差的性能不足1%，我觉得这是非常可以接受的。在工程上可能以后会遇到更多这种情况，当然最后的办法还是找打最优解，但是如果时间和收获比差太大的话选择非最优解也是非常好的选择。所以完成这个功能给我带来最大的收获不是技术层面的，而是编程思想方面的，有时候不一定非要去找到最优解，可能有些东西根本就不存在最优的情况呢；

7.功能4的重点和难点

(1).带分数的出题

较之前的3个功能，最明显的区别就是操作数变了，操作数从整数扩充到了分数，出题的那一部分代码就要发生相应的变化，所以我在生成随机操作数的时候让操作数可以是"5/2"的形式，分数和整数的出现同样是随机的，这样就保证了出的题目中既包括整数也有分数；

(2).带分数题目的计算

带分数题目计算最大的一个难点在于除法是不满足交换律的，也就是"a/b/c"和"a/(b/c)"的结果是不一样的，而分数的表示又和除号是一样的，如果直接按照之前的算法是没有办法完成正确的运算的，需要把分数(a/b)看成是一个数，也就是"a/ b/c"的运算顺序是"a/(b/c)"，这一点看起来容易但实现起来却很困难，反正我俩真的想了好久该怎么解决这一问题。最后我们的解决方案是：把运算数保存到2个数组里，也就是在生成题目的时候，1个数组里的题目是专门用于输出到文件的，就是单纯的字符串形式，另一个数组里的题目是用于计算的，二者的操作数和操作符完全一致，这样就可以实现把分数先计算当做一个数，先完成分数到小数的转换，再重用之前的代码就可以解决，关键代码如下：

number1 = rm.Next(1, 20).ToString();          // 随机生成的分子
number2 = rm.Next(1, 20).ToString();          // 随机生成的分母
randomFractions[i] = number1 + "/" + number2;   // 用于展示的分数字符串
randomRealNum[i] = (Convert.ToDecimal(number1)/Convert.ToDecimal(number2)).ToString();      // 用于计算的操作数

产生题目也产生2个，一个用于输出，一个用于计算：

equation = "(" + " " + nums[0] + " "+ operators[0] + " " + nums[1] + " " + operators[1] + " " + nums[2] + " " + ")" + " " + operators[2] + " " + nums[3] + " " ;    // 用于显示
equationCal = "(" + nums1[0] + operators[0] + nums1[1] + operators[1] + nums1[2] + ")" + operators[2] + nums1[3];  // 用于计算

(3).结果分数约分输出

经过前2个步骤的处理，得到的结果result是string类型的，转化为decimal类型的话，有整数也有小数，对于整数就不用处理可以直接输出，但对于小数就要变成真分数并约分。我们的解决方案是：先正则表达式匹配判断是否为整数，如果为整数则直接可以输出，如果是小数必须经过转化为分数并约分操作。这一步骤是首先把小数的整数部分和小数部分分开，整数部分直接是答案前面的整数数字，小数部分的处理（这里假设是2.5）是根据小数的长度（len =1）让小数除以math.pow(10,len)，也就是10，即得到5和10，然后根据辗转相除法求出这两个数的最大公约数，两个数分别除以最大公约数再按照固定格式输出就可以达到功能预期效果，这部分代码如下：

namespace f4
{
    class DecimalToFraction
    {
        public string decimalTranverse(string value)    // 小数转化为分数
        {
            string result = "";
            string[] str = value.Split('.');
            int decimalLen = str[1].Length;
            if (Regex.IsMatch(str[1], @"^[0]*$"))        //如果小数部分全为0则直接返回整数部分
            {
                return str[0];
            }
            long weitght = Convert.ToInt32(Math.Pow(10, decimalLen));
            long num = Convert.ToInt32(str[1]);
            long gcd = gCD(num, weitght);
            if (Regex.IsMatch(str[0], @"^[+-]?[0]*$"))       // 如果整数部分为0则不用输出整数部分，直接输出分数
            {
                result = String.Format("{0}{1}{2}", num / gcd, "/", weitght / gcd);
            }
            else
            {
                result = String.Format("{0}{1}{2}{3}{4}", str[0], " ", num / gcd, "/", weitght / gcd);

            }

            return result;
        }

        public long gCD(long m, long n)                    //求最大公约数
        {
            long r, t;
            if (m < n)
            {
                t = n;
                n = m;
                m = t;
            }
            while (n != 0)
            {
                r = m % n;
                m = n;
                n = r;

            }
            return (m);
        }

    }
}

8.功能4的编程收获

不要被吓到，看到题目中的要求发现时选做题就觉得这题肯定很难，刚开始真的都很想放弃这个功能了，程序员要女生的青睐反正也没啥用，但是仔细看看好像又没有那么难，所以我们就试着做了一下，结果发现真的没有想象的那么难，跟功能3用的时间根本没法比，所以，做功能4给我最大的收获还是不要被吓到，把功能拆分成几部分然后重用之前的代码也没那么难；还有一个就是我之前一直以为除法是满足结合律的，开始做这个功能的时候就完全没考虑这个事，幸亏队友及时提醒，也让我把最基础的数学巩固了一下；

9.功能5

功能5是为以后做准备，我觉得我们的类和方法重用性都很高，以后会很方便整成接口；

二、结对编程的体会

首先，结对编程可以让人自觉地规范自己的代码风格，我之前的代码命名特别随便，有时候可能还能根据变量要表示的内容给变量起名字，更多情况就是abcd这样起，时不时的还整个拼音上去，所有的函数都写在主函数下面，基本不写注释，导致整个项目乱七八糟，过很短的时间就连自己的代码都看不懂了。结对编程的时候，有个人在你旁边看着刚开始还蛮紧张的，后来反正也是没有自己编的时候那么自由，要命名啥东西被强迫着写注释，写很多个类，类里面再写方法，对编程习惯的改善非常的大；

其次，我是个很粗心的人，有时候没看清要干嘛就开始整了，整出来明明是错的自己也发现不了。结对编程过程中有个人在旁边提醒着就非常有必要，就比如除法那个结合律，要是我自己整肯定就是按照除法遵循结合律做了，但是有队友提醒就能好很多，有些错误自己发现不了，队友很容易就发现了；

第三，可以被督促着干活。平常的话国庆假期可能每天都得睡到10点钟，慢慢悠悠的，但是前一天约好了第二天见面的时间就强行让自己睡不了懒觉，也提高了很多效率；

最后，遇到问题可以随时讨论研究，自己很容易钻到牛角尖里，真正体会到才发现多一条思路是多么重要；

三、花费时间较长，给我较大收获的事件

1.git的使用

之前都是一个项目只有自己提交代码，也很少有冲突，但是结对过程中，有时候用我的电脑，有时候用队友的，经常出现各种提交错误和冲突，有一回还把项目整的打不开了。所以在git的使用上我们多了很多百度的时间，百度报的各种错，最后对git的了解加深了很多，命令也不再局限于add commit push这几个，对报的各种错都有了了解，基本的git问题都能解决；

2.括号匹配

刚开始看到括号匹配的时候我俩主要看的严蔚敏的那版数据结构教材，书上都是伪代码看的头大，王道上更简略，搞清整个算法的流程就花费了非常多的时间（最起码得150分钟），搞清流程后，结合博客转化为C#代码又花费了很多时间（60分钟左右），所幸最后写出来了。这个给我的收获就是弄懂了一个经典算法；

3.单元测试

之前我自己做的测试顶多也就是新建一个工程把一些不太确定的方法在工程里跑一下，这是第一次整正儿八经的单元测试，照着书上和博客上一点一点的弄，虽然不复杂，但是刚开始的时候也是容易丢三落四，忘了很多测试的东西，后来才慢慢好起来，这个测试的入门花了挺多时间，但收获还是蛮大的，终于算是入门测试这一技术了；

4.功能3去重

问了一个比较厉害的同学他说这个功能可以用树的最小生成法来做，所以我们就专门研究树的最小生成法，找书、找博客等各种方法，最后虽然花了非常多的时间（180分钟左右）没整出来就换了个思路，但是在这个过程中，我们还是明白了什么是树的最小生成法，树的同构是怎么回事，也明白了算法的基本原理，甚至去Poj看了题目并提交ac了，也是十分有收获的，也希望今后有时间能继续研究研究这个事；

5.判断一个结果相同的题目操作数和操作符是否相等

因为两个题目结果相同的话这两个题目还不一定是连在一起的，所以需要把所有的题目、题目结果都保存起来，每一个题目的操作数都是数组，操作符也是数组，题目的数量是根据用户输入来的，不知道有多少，所以需要有一个非常好的数据结构来保存这些数据，最开始打算用二维数组，但是二维数组空间分配等有很麻烦，最后用了List<string[]>这一泛型存储数据，非常简便。这让我对泛型的使用和理解又加深了很多，给了我非常大的收获；

要求二：

编程地点：信息科学与技术学院232机房

照片：

---

要求三：

按照老师要求push代码；

作业地址：【https://git.coding.net/zhangjy982/ArithMetic.git】