作业具体要求点 这里
Core组要求：
1.Calc()
这个Calc 函数接受字符串的输入（字符串里就是算术表达式，例如 “5*3.5”，“7/8 - 3/8 ”，“3 + 90 * 0.3”等等），这个模块的返回值是一个字符串。
2.Setting()
在生成四则运算题目之前，需要对一系列属性进行设置，例如生成题目的数量，操作数的数量，题目中操作数的数值的范围，运算符的种类，(+-*/，是否支持真分数运算，是否支持小数运算，是否支持乘方运算……
注：
题目中操作数的数值范围对于真分数来说是指其分母的范围，运算结果可以超出指定范围
当题目中包含小数时，答案亦以小数形式给出，结果为无限小数时保留小数点后两位
乘方运算的幂次方为小于5的自然数
3.Generate()
进行一些设置之后，就可以开始生成所需要的题目了，题目增加以下限制
- 生成的题目计算过程中不能产生负数
例如1 - 2 + 3 =，3 + (4 - 5) =，因为计算过程中产生了负数，都是无效的题目
- 生成的题目中不能包括不必要的括号
例如 1 + (2 * 3)，（1 + 2）+ 3
其中括号为不必要的括号，不能生产此类题目
- 程序一次运行生成的题目不能重复
即任何两道题目不能通过有限次交换+和×左右的算术表达式变换为同一道题目。例如，23 + 45 = 和45 + 23 = 是重复的题目，6 × 8 = 和8 × 6 = 也是重复的题目。3+(2+1)和1+2+3这两个题目是重复的，由于+是左结合的，1+2+3等价于(1+2)+3，也就是3+(1+2)，也就是3+(2+1)。但是1+2+3和3+2+1是不重复的两道题，因为1+2+3等价于(1+2)+3，而3+2+1等价于(3+2)+1，它们之间不能通过有限次交换变成同一个题目。
实现以上接口，编写API文档，供UI组使用（亦可自行增加功能）。
PSP表格：
一、需求分析
①考虑本次作业的主要功能是接受setting、生成表达式，具体的Calc运算函数其实和整体关系不大，优先设计Class和setting。经过商讨，我们决定将Class名定为QuestionCore类，其中设置供setting使用的九个变量：
1.生成问题数量（int）questionNum 初值：40
2.最多操作符数（int）maxOpNum 初值：6
3.算式中数字最小值（int）minData 初值：0
4.算式中数字最大值（int）maxData 初值：15
5.操作符字符串，包括“+-*/^”（string）ops 初值：“+-*/^”，支持乱序输入，根据输入的字符串中包含的运算符进行生成算式
6.是否开启分数运算（bool）fracFlag 初值：true
7.小数精度（int）precise 初值：2
8.题目文件路径 （string）QPath 初值：Questions.txt
9.答案文件路径 （string）APath 初值：Answers.txt
这九个变量足以控制实现作业中的各种要求。同时，设置vector<string>容器的变量来存储结果。相应地设置相关函数。
②考虑生成运算式的方式，想起学习数据结构时“栈”一章里便是将生成运算式作为例题，故重拾谭浩强，初步预定采用栈来生成运算式。后来在组里讨论交流了一下，发现树结构更适合多运算式的随机生成，于是决定以树结构存储、栈形式导出，实现随机生成运算式的功能。树的结点定义结构体，索性定成一个Class：questionNode，其中包含value值、左孩子lchild、右孩子rchild和判别是数字结点还是运算符结点的bool变量opsFlag。
③考虑Calc函数的具体功能，是要对一个输入的式子进行运算，返回string形式的结果。基础运算即不涉及分数的基础四则运算+乘方，通过atoi、to_string等函数不难做到，拆分到CalcNum、CalcStr两个函数中，分别对输入的数字、字符串求解。 追加功能要求支持分数运算，即需要通分、设置带分数等，故加入约分模块，辗转相除法求出最大公约数后进行约分，在Calc中实现。
④考虑封装和对接要求，应该着手学习将CPP封装为dll的方法，并且要及时发布、写好API文档，尽早对接、互相完善。由于接口定义模糊不清，可以预计各组的接口都会有所不同，应当早做准备。
⑤特殊之处：结对编程。需要收集一些结对编程的技巧和经验，合理分工，共同进步。
二、具体设计
①设计两个类：questionNode和questionCore，Node是树节点，如上所述；Core是主要变量和函数的类，包含setting所需的控制变量和实现各种功能的函数。
②Core类中包含树节点Node* questions和string容器Answer，分别负责生成树、存树、操作树与存储生成式子的答案。生成的式子由getQue函数配合对树的操作得到，保存在string 的容器finalQue中。这样我们就可以通过生成一定数目的式子分别将结果和表达式放入Answer和finalQue，达成功能。树的操作有各种结点遍历、检验、转换成string等。
③考虑计算优先级和括号问题。括号要加但不能乱加，我们商量后采用一个比较笨的办法：对每个由其他运算符和数字组建好的式子，先随机生成一定数量的成对括号，找位置往式子里填。填完后，对于无须加括号的，将括号成对删除。此处需要注意的是中途新增需求：乘方运算的右边必须是小于五的自然数，也就是说括号落位还要避免落在乘方后边。
④考虑筛选合格算式问题，由算式中各阶段运算非负，设计isPositive函数来判断是否每一阶段都不为负。设计函数判断两颗运算式树是否在本次作业的意义下等同。由于在树生成和转化时逐个判断算式合格过于繁琐，我们采用过量生成、取用合格算式的策略。若合格算式不够多，则再次生成补充。
⑤考虑对接问题，设计setting函数参数如上所述，设计getResultFile函数，直接将两个vector中的数据分别导出到客户输入的路径下设定的文件中。
三、具体编码
整体文件由question.h、question.cpp、main.cpp组成。question.h中声明了类和各类函数；除了构造和析构函数外，其他函数的实现均在question.cpp中进行。main函数主要用于测试功能。代码分别如下。
头文件已添加预编译头，可编译为dll文件。
#include "Core10.h"
//random a~b
int questionCore::random(int a, int b)
{
return (rand() % (b - a + )) + a;
} //is operator
bool questionCore::isOp(char ch)
{
auto it = find(ops.begin(), ops.end(), ch);
if (it == ops.end())
return false;
return true;
} //is num
bool questionCore::isNum(char ch)
{
if (ch >= ''&&ch <= '')
return true;
return false;
} //is decimal
bool questionCore::isDeci(string str)
{
for (int i = ; i < str.size(); i++)
{
if (str[i] == '.')
return true;
}
return false;
} //op's priority, higher means prior
int questionCore::priority(char op)
{
switch (op)
{
case '#':return -;
case '\0':return -;
case '(':return ;
case ')':return ;//avoid ( ) be put out
case '+':
case '-':return ;
case '*':
case '%':
case '|':
case '/':return ;
case '^':return ;
default:return ;
}
} // return (a op b)
double questionCore::CalcNum(double a, double b, char op)
{
switch (op)
{
case '+':return (a + b);
case '-':return (a - b);
case '*':return (a * b);
case '|':return a / b;
case '/':return a / b;
case '%':return (int)a % (int)b;
case '^':return pow(a, b);
default:return a;
}
} //return answer of que
double questionCore::CalcStr(string & que)
{//OPTR: ops' stack; OPEN: nums' stack
int posTmp = que.find("*-");
if (posTmp != -)
return ;
que.push_back('\0');
stack<char> OPTR; OPTR.push('#');
stack<double> OPEN;
char ch = 'c', chTmp;
double num1, num2;
int pos = ; while (ch != '\0' || OPTR.top() != '#')
{
if (ch != '\0') { ch = que[pos]; pos++; }
if (!isOp(ch) && ch != '\0')
{
if (ch == ' ') continue;
else numPush(OPEN, que, pos);
continue;
}
switch (ch)
{
case '(':OPTR.push(ch); break;
case ')':
chTmp = OPTR.top();
while (chTmp != '(')
{
if (OPEN.empty())
throw "wrong form";
num1 = OPEN.top(); OPEN.pop();
if (OPEN.empty())
throw "wrong form";
num2 = OPEN.top(); OPEN.pop();
OPEN.push(CalcNum(num2, num1, chTmp));
OPTR.pop();
chTmp = OPTR.top();
}
OPTR.pop();
break;
default:
chTmp = OPTR.top();
while (priority(chTmp) >= priority(ch))
{
OPTR.pop();
if (OPEN.empty())
throw "wrong form";
num1 = OPEN.top(); OPEN.pop();
if (OPEN.empty())
throw "wrong form";
num2 = OPEN.top(); OPEN.pop();
OPEN.push(CalcNum(num2, num1, chTmp));
chTmp = OPTR.top();
}
if (ch != '\0')OPTR.push(ch);
break;
}
}
return OPEN.top();
} //push que's nums into stackT
void questionCore::numPush(stack<double> & stackT, string que, int & pos)
{
string strT;
char ch;
while (!isOp(que[pos - ]) && que[pos - ] != '\0')
{
ch = que[pos - ];
strT.push_back(ch);
pos++;
}
pos--;
stackT.push(atof(strT.c_str()));
} //find max divisor
int questionCore::getDivisor(string str)
{
string numTmp;
int times = ;
int divisorTmp = ;
int strLen = str.size();
int backNum = ;
for (int i = ; i < strLen; i++)
{
if (str[i] == '|' || str[i] == '/')
{
if (str[i + ] == '(')
{
i++; while (i <= strLen)
{
if (str[i] == '(')backNum++;
if (str[i] == ')')backNum--;
if (str[i] == '|' || str[i] == '/')divisorTmp *= getDivisor(str.substr(i));
if (divisorTmp == || divisorTmp>maxRange || divisorTmp<)
return ; numTmp.push_back(str[i]);
if (backNum == )break;
i++;
}
}
else
{
while (isNum(str[i + ]) && i + <= strLen)
{
numTmp.push_back(str[i + ]);
i++;
} }
numTmp.insert(, , '(');
times *= int(CalcStr(numTmp.append(")*").append(to_string(int(divisorTmp)))));
if (times == || times>maxRange || times<)
return ;
numTmp.clear();
}
}
if (times == || times>maxRange || times<)
return ;
return times;
} //Euclidean algorithm, zhanzhuanxiangchufa
int questionCore::gcd(int a, int b)
{
if (b != )
return gcd(b, a % b);
else
return a;
} //judge if elems in question are positive
bool questionCore::isPositive(questionNode* root, double &res)
{
double res1 = , res2 = ;
bool flag1, flag2;
if (root == NULL) return false;
if (root->opsFlag == true)
{
flag1 = isPositive(root->lchild, res1);
flag2 = isPositive(root->rchild, res2);
res = CalcNum(res1, res2, char(root->value));
if (res < || res>maxRange)return false;
else return flag1 && flag2;
}
else
{
res = root->value;
return true;
}
} //generate tree from ques, if success return ture
bool questionCore::generateTree(vector<string> & ques)
{
vector<string> res; string que, numStr;
stack<char> OPTR;
stack<questionNode*> OPEN;
questionNode *node1, *node2, *tempNode; for (int i = ; i < ques.size(); i++)
{
que = ques[i];
que.push_back('\0');
OPTR.push('#'); char ch = 'c', chTmp;
int pos = ; while (ch != '\0' || OPTR.top() != '#')
{
if (ch != '\0')ch = que[pos++]; if (!isOp(ch) && ch != '\0')
{
if (ch == ' ') continue;
else
{
while (!isOp(que[pos - ]) && que[pos - ] != '\0')
{
numStr.push_back(que[pos - ]);
pos++;
}
pos--;
tempNode = new questionNode(atoi(numStr.c_str()), false);
OPEN.push(tempNode);
numStr.clear();
}
continue;
}
switch (ch)
{
case '(':OPTR.push(ch); break;
case ')':
chTmp = OPTR.top();
while (chTmp != '(')
{
node1 = OPEN.top(); OPEN.pop();
node2 = OPEN.top(); OPEN.pop();
tempNode = new questionNode(int(chTmp), true, node2, node1);
OPEN.push(tempNode);
OPTR.pop();
chTmp = OPTR.top();
}
OPTR.pop();
break;
default:
chTmp = OPTR.top();
while (priority(chTmp) >= priority(ch))
{
OPTR.pop();
node1 = OPEN.top(); OPEN.pop();
node2 = OPEN.top(); OPEN.pop();
tempNode = new questionNode(int(chTmp), true, node2, node1);
OPEN.push(tempNode);
chTmp = OPTR.top();
}
if (ch != '\0')OPTR.push(ch);
break;
}//switch
}//while
questions.push_back(OPEN.top());
OPEN.pop();
}
return true;
} //judge if 2 trees are the same
bool questionCore::isSame(questionNode* root1, questionNode* root2)
{
if (root1 == NULL && root2 == NULL)
return true;
else if (root1 == NULL || root2 == NULL)
return false; if (root2->value != root1->value)
return false;
else
return isSame(root1->rchild, root2->rchild) && isSame(root1->lchild, root2->lchild);
} //judge if 2 trees are equal
bool questionCore::isEqual(questionNode* root1, questionNode* root2)
{
if (root1 == NULL && root2 == NULL)
return true;
else if (root1 == NULL || root2 == NULL)
return false; bool eFlag1, eFlag2;
if (isSame(root1, root2))
return true;
else
{
eFlag1 = isEqual(root1->lchild, root2->lchild) && isEqual(root1->rchild, root2->rchild);
eFlag2 = isEqual(root1->rchild, root2->lchild) && isEqual(root1->lchild, root2->rchild);
return (eFlag1 || eFlag2) && (root1->value == root2->value);
}
} //judge if tree fit conditions
bool questionCore::judgeTree()
{
int rquesNum = questions.size(); for (int i = ; i < rquesNum; i++)
{
fitFlag[i] = isPositive(questions[i], result[i]);
for (int j = ; j < i; j++)
{
if (result[i] == result[j])
{
if (isEqual(questions[i], questions[j]))
{
fitFlag[i] = false;
isEqual(questions[i], questions[j]);
break;
}
}
}
}
return true;
} //generate questions
vector<string> questionCore::generateQue(int queNum)
{
vector<string> res;
string strTmp;
int num, chOp;
string numStr;
int leftParenPos, rightParenPos;
int opNum, parenNum;
bool isPow = false;
int powFlag = ; for (int i = ; i < queNum; i++)
{
opNum = random(, maxOpNum); for (int j = ; j < opNum; j++)
{
if (isPow == false)
{
num = random(minRange, range);
numStr = to_string(num);
}
else
{
num = random(, );
numStr = to_string(num);
isPow = false;
}
chOp = ops[random(, ops.size() - - powFlag)];
if (char(chOp) == '^')
{
isPow = true;
powFlag = ;
} strTmp.append(numStr);
strTmp.push_back(chOp);
}
num = random(minRange, range);
numStr = to_string(num);
strTmp.append(numStr); parenNum = random(, opNum); for (; parenNum>; parenNum--)
{
leftParenPos = random(, strTmp.size() - );
rightParenPos = random(leftParenPos + , strTmp.size()); while ((leftParenPos != && (!isNum(strTmp[leftParenPos]) || !isOp(strTmp[leftParenPos - ]))) || (leftParenPos != && strTmp[leftParenPos] == '^'))
{
leftParenPos--;
}
strTmp.insert(leftParenPos, , '('); while (rightParenPos != strTmp.size() && (!isNum(strTmp[rightParenPos - ]) || !isOp(strTmp[rightParenPos])))
{
rightParenPos++;
}
strTmp.insert(rightParenPos, , ')');
}
res.push_back(strTmp);
strTmp.clear();
powFlag = ;
}
return res;
} //transform tree to str
void questionCore::treeToStr(questionNode* root, string &pre)
{ if (root == NULL) return;
if (root->opsFlag == false)
{
pre.append(to_string(root->value));
return;
} if (root->lchild->opsFlag == false)
treeToStr(root->lchild, pre);
else if ((priority(root->value) > priority(root->lchild->value)) || (root->value == '^'))
{
pre.push_back('(');
treeToStr(root->lchild, pre);
pre.push_back(')');
}
else
treeToStr(root->lchild, pre); pre.push_back(char(root->value)); if (root->rchild->opsFlag == false)
treeToStr(root->rchild, pre);
else if ((priority(root->value) >= priority(root->rchild->value)) || (root->value == '^'))
{
pre.push_back('(');
treeToStr(root->rchild, pre);
pre.push_back(')');
}
else
treeToStr(root->rchild, pre); return;
} //transform original questions to formal questions
vector<string> questionCore::quesToStr(vector<questionNode*> Quess)
{
string strTmp;
string strExm;
vector<string> finishStr;
int count = ;
int rightNum = ;
bool flag = true;
int dot = ;
bool flag2 = true; for (int i = ; i < Quess.size(); i++)
{
treeToStr(Quess[i], strTmp);
for (int j = ; j<strTmp.size() - ; j++)
if (strTmp[j] == '^')
if ((strTmp[j + ] > '') || (strTmp[j + ] == '('))
{
flag = false; break;
}
if (!flag) {
strTmp.clear();
flag = true;
continue;
}
strExm = Calc(strTmp);
for (int j = ; j < strExm.size(); j++) {
if (strExm[j] == '\'') dot = j;
if (strExm[j] == '|')
if (j - dot > || strExm.size() - j > )
flag2 = false;
}
if (!flag2) {
strTmp.clear();
strExm.clear();
flag2 = true;
dot = ;
continue;
} finishStr.push_back(strTmp);
strTmp.clear();
count++;
if (count >= quesNum)
break;
}
return finishStr;
} //below:public function //free and reset
bool questionCore::Clear() {
int Num = questions.size();
for (int i = ; i < Num; i++)
{
questionNode* temp = questions[i];
deleteQues(temp);
}
questions.clear();
Answer.clear();
return true;
} //get real fraction and return result
string questionCore::Calc(string inQues)
{
int devisor;
int intNum;
string tpQues;
long res; if (fracFlag == true) {
devisor = getDivisor(inQues); if (fracFlag&&devisor > && devisor < maxRange && !isDeci(inQues))//get the real fraction
{
tpQues.append(to_string(devisor));
tpQues.append("*(");
tpQues.append(inQues).push_back(')');
res = int(CalcStr(tpQues));
intNum = gcd(res, devisor);
tpQues = to_string(int(res / intNum));
if (devisor / intNum != )
{
if (res > devisor)
{
tpQues.clear();
tpQues.append(to_string(int(res / devisor))).append("'").append(to_string(int(res / intNum - int(res / devisor)*(devisor / intNum)))).append("|").append(to_string(devisor / intNum));
}
else
tpQues.append("|").append(to_string(devisor / intNum));
}
return tpQues;
}
else
{
tpQues = to_string(CalcStr(inQues));
for (int i = ; i < - precise; i++)
tpQues.pop_back();
if (precise == )
tpQues.pop_back();
return tpQues;
}
}
//if not fraction
else {
tpQues = to_string(CalcStr(inQues));
for (int i = ; i < - precise; i++)//set precise
tpQues.pop_back();
if (precise == )
tpQues.pop_back();
return tpQues;
}
} //get questions
vector<string> questionCore::getQues() { vector<string> originQues;
vector<questionNode*> judgedQues;
vector<string> finalQues, tempQues; originQues = generateQue( * quesNum);
//generate 10 times questions and choose 1/10 from them
/*for (int i = 0; i < originQues.size()-1; i++) {
if (originQues[i].find("^("))
for (int j = i; j < originQues.size() - 2; j++)
originQues[j] = originQues[j + 1];
}*/
/*for (vector<string>::iterator it = originQues.begin();it != originQues.end();)
{
if ((*it).find("^("))
//删除指定元素，返回指向删除元素的下一个元素的位置的迭代器
it = originQues.erase(it);
else
//迭代器指向下一个元素位置
++it;
}*/ generateTree(originQues);
judgeTree();//build and judge for (int i = ; i < questions.size(); i++)
{
if (fitFlag[i] == true)
judgedQues.push_back(questions[i]);
} finalQues = quesToStr(judgedQues); for (int i = ; i < finalQues.size(); i++)
{
Answer.push_back(Calc(finalQues[i]));
} //add ' ' between ops and nums
string strTmp;
for (int i = ; i < finalQues.size(); i++)
{
strTmp = finalQues[i];
for (int j = ; j < strTmp.size(); j++)
{
if (strTmp[j] == '|'&&fracFlag == true) continue; else if (isOp(strTmp[j]) && strTmp[j] != '('&&strTmp[j] != ')')
{
strTmp.insert(j, , ' ');
strTmp.insert(j + , , ' ');
j += ;
}
}//for
finalQues[i] = strTmp;
}//for return finalQues;
} //get answers
vector<string> questionCore::getAns() {
return Answer;
} //setting
bool questionCore::setting(int queNum = , int maxOpnum = , int MinR = , int MaxR = , string op = "+-*/^", bool fraction = true, int preci = , string QPath = "Questions.txt", string APath = "Answers.txt")
{
quesNum = queNum;
maxOpNum = maxOpnum;
minRange = MinR;
range = MaxR;
ops.clear();
for (int i = ; i < op.size(); i++)
{
ops.push_back(op[i]);
}
fracFlag = fraction;
precise = preci;
QuePath = QPath;
AnsPath = APath;
setOps();
return true;
} //add ( ) into ops . if fraction, add function
void questionCore::setOps() {
if (fracFlag)
ops.insert(ops.end(), '|');
ops.insert(ops.end(), , '(');
ops.insert(ops.end(), , ')');
} //getResultFile, output Questions.txt , Answers.txt
void questionCore::getResultFile() {
vector<string> Ques = getQues();
vector<string> Ans = getAns(); ofstream foutQues;
foutQues.open(QuePath, ios::out);
for (int i = ; i < Ques.size(); i++) {
foutQues << Ques[i] << endl;
}
foutQues.close(); ofstream foutAns;
foutAns.open(AnsPath, ios::out);
for (int i = ; i < Ans.size(); i++) {
foutAns << Ans[i] << endl;
}
foutAns.close();
Clear();
}
question.cpp
#include "question.h"
using namespace std; int main()
{
questionCore Work(); Work.setting(, , , , "+-*/^", true, );//num of questions, num of ops, min of nums, max of nums, ops(+-*/^), if need fraction, precise
// int int int int string bool int
Work.getResultFile(); return ;
}
main.cpp
函数前均已写明功能，实现过程并不算复杂，变量名调整得更易读了。
四、测试
测试环节由我们2人分工，各自出样例导入setting，观察输出函数结果的情况。有一次结果中突然多了一些负数，我debug半天百思不得其解，队友却很快提醒我：我把CalNum函数中变量的先后顺序搞错了，运算数与被运算数换了位置。这让我节省了非常多的时间。经过重重磨难，我们相互督促、相互鼓励，终于将大部分功能基本完成，需要学习dll等待对接。cpp转dll可以说是我遇见过的最坑的博客问题群，各博主们都在教“一加一”，却没有一份教程详细告诉我们成型的cpp和h文件要怎么转换为dll。因此，我们又花费了大量时间摸索dll文件的制作，比其他组慢了一拍。最后，还是组里的一位同学给了我们帮助，让我们得以从繁琐蒙蔽的dll误导中走出来。今后有空，我要写一份真正有用的cpp转dll博客，不让这样的悲剧再发生。
对接时，我们先找了组里的一队UI，面对面对接，但他的QT似乎有点问题，经过他一段时间的升级编译器后，我们总算有惊无险地对接成功。随后，我们将头文件、dll和lib文件和API文档保存在压缩文件中，发布到群里，目前它正在等待可爱善良帅气大方好心的UI组宠幸。
五、结对
①结对编程在这次作业中最直接的好处就是干的活少了，一起讨论、设计完函数后可以共同实现、轮班，相互测试，完成效率比较高。同时，由于一人编码、一人监督，bug率大大降低，有一次我的if函数中犯了个很低级的逻辑错误，立马就被队友机智地识破并指出，省去了巨大的debug时间开销。
②从这次结对中，我学到了敢于担当、积极进取的精神，学会了与他人一同合作、共同开发软件，也发现了自己知识层面的许多不足，需要继续努力。
③今后工作中若有机会，我会选择结对编程。
图为我帮队友同步审核代码
六、总结反思
本次结对编程中的收获上文中也说得差不多了，补充一点：学到了dll的相关知识且打算抽空写一篇cpp转dll攻略。总的来说还有一些做得不够好的地方，比如接口的设计除了兼容文件输入、字符串输入外，还能更加人性化一点、增加更多功能方便UI组调用等等，但由于时间确实紧张，没能实现多少。
对于这门课的看法，我认为这门课确实比较锻炼动手能力，但很多时候一些通知和需求下发得比较晚，任务也比较重，对我们的负担还是相当大的。在有个人作业、结对作业的周，我根本没有时间去碰我们的团队作业，还一定程度上影响了我正常的课业学习。但总体而言，我还是比较喜欢这门课的，希望以后的团队作业中，我们组能同心协力、共创佳绩。