用于作业记录和复习

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;//Link的节点结构class SNode{public:	int data;	SNode *next, *ahead;	static SNode *freeNodeLink;//freeList技术，重用弃用空间，提高效率	SNode()	{		next = NULL;		ahead = NULL;	}	~SNode(){}		/**	 *new操作符重载，充分利用之前弃用在Link::freeLink的SNode结点	 **/	void* operator new(size_t)	{		if (freeNodeLink == NULL) return ::new SNode;		SNode* newTemp = freeNodeLink;				if (freeNodeLink->next == NULL)			freeNodeLink = NULL;		else		{			freeNodeLink = freeNodeLink->next;			freeNodeLink->ahead = NULL;		}		newTemp->ahead = NULL;		newTemp->next = NULL;		newTemp->data = 0;		return newTemp;	}	/**	 *delete操作符重载	 **/	void operator delete(void* delNode)	{		SNode* delTemp = (SNode*)delNode;		delTemp->ahead->next = delTemp->next;		if (delTemp->next != NULL)		{			delTemp->next->ahead = delTemp->ahead;		}				if (freeNodeLink == NULL)		{			freeNodeLink = delTemp;		}		else		{			delTemp->ahead = freeNodeLink;			delTemp->next = freeNodeLink->next;			if (delTemp->next != NULL)				delTemp->next->ahead = delTemp;			delTemp->ahead->next = delTemp;		}			}};//ResultLink的节点结构class RNode{public:	string value;	RNode *next, *ahead;	static RNode *freeRNodeLink;//freeList技术，重用弃用空间，提高效率	RNode()	{		next = NULL;		ahead = NULL;	}	~RNode(){}	/**	 *new操作符重载	 **/	void* operator new(size_t)	{		if (freeRNodeLink == NULL) return ::new RNode;		RNode* newTemp = freeRNodeLink;				if (freeRNodeLink->next == NULL)			freeRNodeLink = NULL;		else		{			freeRNodeLink = freeRNodeLink->next;			freeRNodeLink->ahead = NULL;		}		newTemp->ahead = NULL;		newTemp->next = NULL;		newTemp->value = "";		return newTemp;	}	/**	 *delete操作符重载	 **/	void operator delete(void* delNode)	{		RNode* delTemp = (RNode*)delNode;		delTemp->ahead->next = delTemp->next;		if (delTemp->next != NULL)		{			delTemp->next->ahead = delTemp->ahead;		}				if (freeRNodeLink == NULL)		{			freeRNodeLink = delTemp;		}		else		{			delTemp->ahead = freeRNodeLink;			delTemp->next = freeRNodeLink->next;			if (delTemp->next != NULL)				delTemp->next->ahead = delTemp;			delTemp->ahead->next = delTemp;		}	}};//字符链表，封装了多种功能class Link{private:	SNode *head, *trail;	int linkLength;public:	//构造函数	Link()	{		head = NULL;		trail = NULL;		linkLength = 0;	}	//构造函数	Link(string number)	{		head = NULL;		trail = NULL;		linkLength = 0;		createLink(number);	}	//构造函数	Link(Link *&link)	{		head = new SNode;		trail = new SNode;		linkLength = 0;		copyLink(link);	}	~Link(){}	//创建链表	void createLink(string number)	{		bool isFirst = true;		int zeroCount = 0;		int realNumberIndex = 0;		int length = number.length();		for (int i = 0; i < length; i++)		{			if (number[i] != '0' && isFirst)//第一个非零数的下标			{				realNumberIndex = i;				isFirst = false;			}			if (number[i] == '0')//零的个数				zeroCount++;		}					if (zeroCount == number.length())//判断是否为0			addNode(0);		else		{			string s = number.substr(realNumberIndex, length);			int tempLength = s.length();			for (int i = 0; i < tempLength; i++)				addNode(s[i]-'0');		}	}	//创建结点	void addNode(int data)	{		if (head == NULL)//如果表为空		{			head = new SNode;			head->data = 0;			head->next = NULL;			head->ahead = NULL;			SNode *newNode = new SNode;			newNode->data = data;			newNode->next = NULL;			newNode->ahead = head;						head->next = newNode;			reSetTrail();		}		else//如果表存在一个以上结点SNode		{			reSetTrail();			SNode *newNode = new SNode;			newNode->data = data;			newNode->next = NULL;			newNode->ahead = trail;			trail->next = newNode;			reSetTrail();		}		linkLength++;	}	//创建结果结点	void addResultNode(int data)	{		if (head == NULL)//如果表为空		{			//生成头指针			head = new SNode;			head->data = 0;			head->next = NULL;			head->ahead = NULL;			//生成头结点			SNode *newNode = new SNode;			newNode->data = data;			newNode->next = NULL;			//头结点指向头指针			newNode->ahead = head;			//头指针指向头结点			head->next = newNode;			//尾指针指向对结点			trail = head->next;		}		else//如果表存在一个以上结点SNode		{			//生成新的头结点			SNode *newNode = new SNode;			newNode->data = data;			//新的头结点指向旧的旧的头结点			newNode->next = head->next;			//新的头结点指向头指针			newNode->ahead = head;			//旧的头结点指向新的头结点			head->next->ahead = newNode;			//头指针指向新的头结点			head->next = newNode;			//下面两个语句把尾指针移到最后一个结点			trail = head->next;			reSetTrail();		}		//结点的个数加一		linkLength++;	}	//输出测试	void output()	{		trail = head->next;		while (trail != NULL)		{			cout<
         
          data;			trail=trail->next;		}		cout<
          
           next; while (trail != NULL) { ss<
           
            data; trail = trail->next; } return ss.str(); } //返回int int toInteger() { int count = 0; int temp_Result = 0; reSetTrail(); while (!isTrailAtFirst()) { int a = (int)pow(10,count); int b = getTrail()->data*a; temp_Result = b + temp_Result; trailMoveAhead(); count++; } return temp_Result; } /** *让尾指针复位，指向最后一个结点 **/ void reSetTrail() { trail = head->next; while(trail->next != NULL) trail = trail->next; } //链表长度 int getLenght() { return linkLength; } //设置链表长度 void setLength(int length) { linkLength = length; } SNode* getHead() { return head; } void setHead(SNode *pHead) { head->ahead = pHead->ahead; head->data = pHead->data; head->next = pHead->next; } SNode* getTrail() { return trail; } //获得尾指针 void setTrail(SNode *pTrail) { if (pTrail != NULL) { trail->ahead = pTrail->ahead; trail->data = pTrail->data; trail->next = pTrail->next; } } //尾指针前移一个结点 void trailMoveAhead() { if(trail->ahead != NULL) trail = trail->ahead; } //判断尾指针是否在第一个结点 bool isTrailAtFirst() { if(trail->ahead == NULL) return true; else return false; } //把要删除的链表放在Link::freeLinkList里面 void operator delete(void* delLink) { Link* delTemp = (Link*)delLink; if (SNode::freeNodeLink == NULL) SNode::freeNodeLink = delTemp->head; else { delTemp->head->ahead = SNode::freeNodeLink; delTemp->trail->next = SNode::freeNodeLink->next; if (SNode::freeNodeLink->next != NULL) { SNode::freeNodeLink->next->ahead = delTemp->trail; SNode::freeNodeLink->next = delTemp->head; } } delTemp->head = NULL; delTemp->trail = NULL; delTemp = NULL; } //链表拷贝 void copyLink(Link *&link) { link->reSetTrail(); setHead(link->head); setTrail(link->trail); setLength(link->linkLength); }};//用来格式化输出易读日常数学表达式class ResultLink{public: RNode *head, *trail; int addCount; ResultLink() { head = NULL; trail = NULL; addCount = 0; } //增加结点 void addNode(string value) { if (head == NULL)//如果表为空 { head = new RNode; head->value = ""; head->next = NULL; head->ahead = NULL; RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = head; head->next = newNode; reSetTrail(); } else//如果表存在一个以上结点SNode { reSetTrail(); RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = trail; trail->next = newNode; reSetTrail(); } } //在开始插入一个结点 void addFirstNode(string value) { if (head == NULL)//如果表为空 { head = new RNode; head->value = ""; head->next = NULL; head->ahead = NULL; RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = head; head->next = newNode; reSetTrail(); } else//如果表存在一个以上结点SNode { RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = head; newNode->next = head->next; head->next->ahead = newNode; head->next = newNode; reSetTrail(); } } //在末尾增加结点 void addLastNode(string value) { if (head == NULL)//如果表为空 { head = new RNode; head->value = ""; head->next = NULL; head->ahead = NULL; RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = head; head->next = newNode; reSetTrail(); } else//如果表存在一个以上结点SNode { trail = head->next; reSetTrail(); RNode *newNode = new RNode; newNode->value = value; newNode->next = NULL; newNode->ahead = trail; trail->next = newNode; trail = trail->next; } } //形成一个表达式 void addExpression(string left, string symbol, string right) { if (isAdded()) addExpreesionLater(symbol, right); else { addFirstNode("("); addNode(left); addNode(symbol); addNode(right); addLastNode(")"); } addCount++; } //拼接成一个表达式 void addExpreesionLater(string symbol, string right) { addFirstNode("("); addNode(symbol); addNode(right); addLastNode(")"); } //去掉前后的括号 void delBrackets() { delete head->next; reSetTrail(); delete trail;// delete trail->next; } //判断有没有增加过表达式 bool isAdded() { if (addCount == 0) return false; else return true; } //把要删除的链表放在Link::freeLinkList里面 void operator delete(void* delLink) { ResultLink* delTemp = (ResultLink*)delLink; if (RNode::freeRNodeLink == NULL) RNode::freeRNodeLink = delTemp->head; else { delTemp->head->ahead = RNode::freeRNodeLink; delTemp->trail->next = RNode::freeRNodeLink->next; if (RNode::freeRNodeLink->next != NULL) { RNode::freeRNodeLink->next->ahead = delTemp->trail; RNode::freeRNodeLink->next = delTemp->head; } } delTemp->head = NULL; delTemp->trail = NULL; delTemp = NULL; } /** *让尾指针复位，指向最后一个结点 **/ void reSetTrail() { trail = head->next; while(trail->next != NULL) trail = trail->next; } //返回string string toString() { stringstream ss; trail = head->next; while (trail != NULL) { ss<
            
             value; trail = trail->next; } return ss.str(); }};//栈，用来存储字符链表以及辅助实现各种运算class Strack{private: Link** linkStrack; int top; int size;public: Strack(int initSize = 100) { size = initSize; top = 0; linkStrack = new Link*[initSize]; } ~Strack() { delete [] linkStrack; } //压入 bool push(Link*& item) { if (top == size) return false; //栈满 else { linkStrack[top++] = item; return true; } } //弹出 bool pop(Link*& item) { if (top == 0) return false;//栈空 else { item = linkStrack[--top]; return true; } } //判断栈顶是否有压入的元素 bool topValue(Link*& item) const { if (top == 0) return false;//栈空 else { item = linkStrack[top-1]; return true; } } //栈的长度 int length() const { return top; }};//为大作业写的String的工具类class StringUtil{public: /********************************************************** *功能：去前后空格 *str：字符串 *反回值：去除前后空格后的字符串 ***********************************************************/ static std::string trim(string str) { string::size_type pos = str.find_last_not_of(' '); if(pos != string::npos)//如果找到非空格字符 { str.erase(pos + 1); pos = str.find_first_not_of(' '); if(pos != string::npos)//如果找到非空格字符 str.erase(0, pos); } else str.erase(str.begin(), str.end()); //如果全部是空格，则删除全部空格 return str; } /********************************************************** *功能：去前后空格 *str：源字符串 *反回值：去除前后空格后的字符串 ***********************************************************/ static std::string trim_quote(string& str) { string::size_type pos = str.find_last_not_of(' '); if(pos != string::npos)//如果找到非空格字符 { str.erase(pos + 1); pos = str.find_first_not_of(' '); if(pos != string::npos)//如果找到非空格字符 str.erase(0, pos); } else str.erase(str.begin(), str.end()); //如果全部是空格，则删除全部空格 return str; } /********************************************************** *功能：读取每个数据 *str：源字符串 *反回值：一个数据 ***********************************************************/ static std::string findNextWord(string& str) { string::size_type startPos = str.find_first_not_of(' ');//第一个不为空格的地方 string::size_type endPos = str.find_first_of(' ',startPos);//从不为空格的地方开始找到第一个为空格的地方 string word = str.substr(startPos, endPos);//获得词的string endPos = str.find_first_not_of(' ', endPos); str.erase(startPos, endPos); return word; }};class Caculator{public: //正确读入表达式，并计算出表达式的结果，输出到outputFile.txt文件内 void caculateExpressions(string filePath_in, string filePath_out) { ifstream inputFile; ofstream outputFile; inputFile.open(filePath_in,ios::in); outputFile.open(filePath_out, ios::out); if (!inputFile.is_open()) { cout<<"打开文件失败"<
             
              push(newWord); } else { if (strLinkStrack->length() > 1) { Link *left,*right,*result; strLinkStrack->pop(left); strLinkStrack->pop(right); if (word == "+") { //cout<<"41:"<<"加法"<
              
               addExpression(left->toString(), word, right->toString());//left:弹出的第一个数，word:运算符,right:弹出的第二个数// outputFile<<"("<
               
                toString()<
                
                 <
                 
                  toString()<<")";// outputss<<"("<
                  
                   toString()<
                   
                    <
                    
                     toString()<<")"; result = caculate(left, right, word); } else if (word == "*") { //cout<<"42:"<<"乘法"<
                     
                      addExpression(left->toString(), word, right->toString());//left:弹出的第一个数，word:运算符,right:弹出的第二个数// outputFile<<"("<
                      
                       toString()<
                       
                        <
                        
                         toString()<<")";// outputss<<"("<
                         
                          toString()<
                          
                           <
                           
                            toString()<<")"; result = caculate(left, right, word); } else if (word == "^") { //cout<<"43:"<<"幂"<
                            
                             addExpression(right->toString(), word, left->toString());//left:弹出的第一个数，word:运算符,right:弹出的第二个数// outputFile<<"("<
                             
                              toString()<
                              
                               <
                               
                                toString()<<")";// outputss<<"("<
                                
                                 toString()<
                                 
                                  <
                                  
                                   toString()<<")"; result = caculate(right, left, word); }// string temp = resultLink->toString();// cout<
                                   
                                    <
                                    
                                     push(result); } else { cout<<"Error!==>>"<
                                     
                                      toString()<
                                      
                                       length() != 0) { Link *resultOutput; strLinkStrack->pop(resultOutput); cout<
                                       
                                        toString()<<" "; rest.append(resultOutput->toString()); rest.append(" "); } cout<
                                        
                                         >the error is after "<
                                         
                                          toString()<
                                          
                                           <
                                           
                                            length() == 1) { Link *resultOutput; strLinkStrack->pop(resultOutput); resultLink->delBrackets(); resultLink->addNode("="); resultLink->addNode(resultOutput->toString()); outputFile<
                                            
                                             toString()<
                                             
                                              <
                                              
                                               >the error is after "<
                                               
                                                toString()<
                                                
                                                 length() != 0) { Link *resultOutput; strLinkStrack->pop(resultOutput); cout<
                                                 
                                                  toString()<<" "; rest.append(resultOutput->toString()); rest.append(" "); } cout<
                                                  
                                                   >"<
                                                   
                                                    toString()<
                                                    
                                                     <
                                                     
                                                      reSetTrail(); rightNumber->reSetTrail(); /*if (leftNumber->getLenght() > rightNumber->getLenght()) {*/ while(!leftNumber->isTrailAtFirst() || !rightNumber->isTrailAtFirst()) { temp_result = leftNumber->getTrail()->data + rightNumber->getTrail()->data + carry; /*if (!rightNumber->isTrailAtFirst()) { temp_result = leftNumber->getTrail()->data + rightNumber->getTrail()->data + carry; } else { temp_result = leftNumber->getTrail()->data + carry; }*/ newLink->addResultNode(temp_result%10); carry = temp_result/10; leftNumber->trailMoveAhead(); rightNumber->trailMoveAhead(); } if (carry != 0) { newLink->addResultNode(carry); } /*} else { while (!rightNumber->isTrailAtFirst() && carry == 0) { if (!leftNumber->isTrailAtFirst()) { temp_result = rightNumber->getTrail()->data + leftNumber->getTrail()->data + carry; } else { temp_result = rightNumber->getTrail()->data + carry; } if (temp_result > 9) { newLink->addResultNode(temp_result-10); carry = 1; } else { newLink->addResultNode(temp_result); carry = 0; } leftNumber->trailMoveAhead(); rightNumber->trailMoveAhead(); } }*/ leftNumber->reSetTrail(); rightNumber->reSetTrail(); return newLink; } //乘法运算 Link* multi(Link *&leftNum, Link *&rightNumber) { Link *leftNumber = leftNum; if (leftNumber == rightNumber) { leftNumber = new Link(rightNumber); } int carry = 0;//存贮进位 int temp_result = 0; Caculator caculator; int length = 0;//最短乘数的长度 string *totalNumbers;// string lastResult; Link *lastResult; stringstream ss; if (leftNumber->getLenght() > rightNumber->getLenght()) { length = rightNumber->getLenght(); totalNumbers = new string[length]; int lenCount = 0; rightNumber->reSetTrail(); while (!rightNumber->isTrailAtFirst() && lenCount != length) { ss.str(""); leftNumber->reSetTrail(); while (!leftNumber->isTrailAtFirst()) { temp_result = leftNumber->getTrail()->data * rightNumber->getTrail()->data + carry; string temp = ss.str(); ss.str(""); ss << (temp_result%10); ss << temp; carry = (temp_result/10); leftNumber->trailMoveAhead(); } if (carry != 0) { string temp = ss.str(); ss.str(""); ss << carry; ss << temp; } for (int i = 0; i < lenCount; i++) ss << '0'; totalNumbers[lenCount] = ss.str(); lenCount++; rightNumber->trailMoveAhead(); } lastResult = new Link(totalNumbers[0]); for (int i = 1; i < length; i++) { Link *addedLink = new Link(totalNumbers[i]); Link *temp = caculator.add(lastResult, addedLink); delete lastResult; lastResult = temp; delete addedLink; //delete temp; addedLink = NULL; temp = NULL; } } else { length = leftNumber->getLenght(); totalNumbers = new string[length]; int lenCount = 0; leftNumber->reSetTrail(); while (!leftNumber->isTrailAtFirst() && lenCount != length) { ss.str(""); rightNumber->reSetTrail(); while (!rightNumber->isTrailAtFirst()) { temp_result = leftNumber->getTrail()->data * rightNumber->getTrail()->data + carry; string temp = ss.str(); ss.str(""); string temp1 = ss.str(); ss << (temp_result%10); string temp2 = ss.str(); ss << temp; string temp3 = ss.str(); carry = (temp_result/10); rightNumber->trailMoveAhead(); } if (carry != 0) { string temp = ss.str(); ss.str(""); ss << carry; ss << temp; } for (int i = 0; i < lenCount; i++) ss << '0'; totalNumbers[lenCount] = ss.str(); lenCount++; leftNumber->trailMoveAhead(); } lastResult = new Link(totalNumbers[0]); for (int i = 1; i < length; i++) { Link *addedLink = new Link(totalNumbers[i]); Link *temp = caculator.add(lastResult, addedLink); delete lastResult; lastResult = temp; delete addedLink; //delete temp; addedLink = NULL; temp = NULL; } } return lastResult; } //幂运算 Link* exp(Link *&baseNumber, Link *&rightNumber) { Link *base = baseNumber; if (base == rightNumber) { base = new Link(rightNumber); } Link *lastResult = new Link("1"); Caculator caculator; int exponentNumber = rightNumber->toInteger(); for (int i = 0; i < exponentNumber; i++) { lastResult = caculator.multi(lastResult, base); }/* cout<<"exponentNumber"<
                                                      
                                                       <
                                                       
                                                        toString()<<"*"<
                                                        
                                                         toString(); lastResult = caculator.multi(lastResult, base); cout<<"="<
                                                         
                                                          toString()<
                                                          
                                                           toString()<<"*"<
                                                           
                                                            toString(); Link* temp = caculator.multi(base,base); delete base; base = NULL; base = temp;// string test = base->toString();// cout<<"="<
                                                            
                                                             <
                                                             
                                                              >= 1; cout<<"exponentNumber:3:"<
                                                              
                                                               <