字符串处理大数据总结
字符串处理大数据小结
字符串处理大数据小结
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客:google搜索“cqs_2012”即可;
个人爱好:酷爱数据结构和算法,希望将来搞科研为人民作出自己的贡献;
博客内容:字符串处理大数据小结;
博客时间:2014-3-27
编程语言:C++
编程坏境:Windows
编程工具:vs2008
-
引言
今天本想做题的,把英雄会上一个题目做出来,后来发现要用到自己以前写过的字符串处理函数,故就把以前的字符串函数总结一下,写了一些简明的注释,方便自己和大家用,特分享于此。
-
知识总结
1.我们都知道整形数据是有范围限制的,当超过整形表示范围后,可能溢出,所以用强大的字符串来处理大型数据是非常有用的,我们不着急于我们怎么去处理大数据,从小的做起,用字符串的形式模拟两个整数相加
程序结果演示如下
看完结果感觉还行吧,说明如下
// function 1: mode the add of int( (-3) + (-3) ) = - 6 // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相加操作,结果存在返回的字符串里
代码如下// mode the add of int string String::ADD_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input ADD_Int"; } Standardization(a); Standardization(b); if(a[0] != '-' && b[0] != '-') return AddInt(a,b); else if(a[0] != '-'&& b[0] == '-') return MinusInt( a,b.substr( 1,b.size() ) ); else if(a[0] == '-'&& b[0] != '-') return MinusInt(b,a.substr(1,a.size())); else return '-'+AddInt(a.substr(1,a.size()),b.substr( 1,b.size() )); };
2.整形大数程序结果截图如下
代码说明如下
// function 2: make a-b mode int a - b; 7 - (-3) = 10 // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相减操作,结果存在返回的字符串里
算法代码如下// make a-b mode int a - b; string String::MINUS_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input Multiplies_Int"; } Standardization(a); Standardization(b); if(a[0] != '-' && b[0] != '-') return MinusInt(a,b); else if(a[0] != '-' && b[0] == '-') return AddInt(a,b.substr(1,b.size())); else if(a[0] == '-' && b[0] != '-') return "-"+AddInt(a.substr(1,a.size()),b); else return MinusInt( b.substr(1,b.size()) , a.substr(1,a.size()) ); };
3.整形大数相乘程序运行结果如下
函数说明如下
// input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相乘操作,结果存在返回的字符串里
算法代码如下;// make a*b mode int a * b; string String::MULT_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input Multiplies_Int"; } Standardization(a); Standardization(b); string::size_type i = a.size(),j = b.size(); string c = "0",d = ""; bool fushu = (a[0] == '-' && b[0] != '-')||(a[0] != '-' && b[0] == '-'); if(a[0] == '-') a = a.substr(1,a.size()); if(b[0] == '-') b = b.substr(1,b.size()); int jinwei = 0; for( j = b.size()-1 ; j < b.size() ;j--) { // each number of b to * a jinwei = 0; for( i = a.size()-1 ; i < a.size() ;i-- ) { d = IntToChar( ( CharToNumber(a[i]) * CharToNumber(b[j]) + jinwei ) % 10 )+ d ; jinwei = ( CharToNumber(a[i]) * CharToNumber(b[j]) + jinwei ) / 10 ; } if(jinwei) d = IntToChar(jinwei) +d; // add all number result c = ADD_Int(c,d); d = ""; unsigned int zero = 0 ; while( zero < b.size() - j ) { d = d + '0'; zero ++; } } Standardization(c); if( fushu && c != "0" ) return '-'+c; else return c; };4.整形大数做除法
程序运行如下
函数说明性文档如下
// function 4: mode the division a/b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相除操作,结果存在返回的字符串里
算法代码实现如下// mode the division a/b string String::DIV_Int(string a,string b) { // exception of input if( a.empty() ) return "0"; else if( b.empty() ) return "e"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input DIV_Int"; } Standardization(a); Standardization(b); if(b == "0") return "e"; bool fushu = (a[0] == '-' && b[0] != '-')||(a[0] != '-' && b[0] == '-'); if( a[0] == '-' ) a = a.substr(1,a.size()); if( b[0] == '-' ) b = b.substr(1,b.size()); if( Compare(a,b) == '<' ) return "0"; string yushu = ""; string beichushu = a.substr(0,b.size()); string shang = Division( beichushu , b); yushu = MinusInt( beichushu ,MULT_Int( shang, b) ); string c = shang; for(string::size_type i = b.size(); i<a.size(); i++) { // beichushu = (yushu * 10 + a.substr(i,b.size())) // shang = beichushu/ b; // c = c + shang; // yushu = beichushu - b* shang; beichushu = yushu+ a[i] ; shang = Division( beichushu , b); c = c + shang; yushu = MinusInt( beichushu ,MULT_Int( shang, b) ); } Standardization(c); return fushu?('-'+c):c; };
5.指数运算程序运行结果如下
哥们,看到这你有什么感想?别喷我是疯子,我也不怕喷,我就是疯子,是疯子推动了IT行业的发展。
哈哈,函数说明如下
// function 5: pow number a^b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的a^b操作,结果存在返回的字符串里
算法代码演示如下// function: pow number x,y string String::Pow_Int(string a,string b) { // exception of input if( a.empty() ) return "0"; else if( b.empty() ) return "e"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input DIV_Int"; } Standardization(a); Standardization(b); string result = "1" ; if(Compare(b,"0") != '<') for(string i ="0" ;Compare(i,b) == '<' ;i = AddInt(i,"1")) { result = MULT_Int(result,a); } else for(string i ="0" ;Compare(i,b) == '>' ;i = MINUS_Int(i,"1")) { result = DIV_Int(result,a); } return result ; };
6.整形数转换成字符串格式程序运行结果如下
如果输入小数会如下
显然很不理想哈
函数文档说明如下
// function 6: int To string :"123" = 123 // input: 一个int数 a; // output: 返回一个字符串,字符串里面是整数; // 功能: 将整数a转换成对应的字符串格式
算法代码实现如下// function : int To string string String::Int_To_String(int x) { bool fushu = false; string result=""; if(x < 0 ) { fushu = true ; x = -x; } else if( x == 0 ) return "0"; while(x) { result = IntToChar(x % 10) + result; x = x/10; } if(fushu) result = "-"+result; return result; };
7.实现比较操作程序运行结果如下
函数说明性文档如下
// function 13: compare string a and b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符,字符里是a和b的大小关系; // 功能: 实现参数两个整数的a和b比较操作,结果< or = or >存在返回的字符里
算法代码实现如下// compare string a and b char String::Compare(string a,string b) { if(a.empty() || b.empty()) { cout<<"error of input compare"; return 'e'; } else { if(!check_all_number(a) || !check_all_number(b)) { return 'e'; } Standardization(a); Standardization(b); if(a[0] == '-' && b[0] != '-') return '<'; else if( a[0] != '-' && b[0] == '-') return '>'; bool fushu = (a[0] == '-'); if(a.size() > b.size() ) return fushu?'<':'>'; else if(a.size() == b.size()) { for(string::size_type i = 0;i < a.size(); i++) { if(a[i] > b[i]) return fushu?'<':'>'; if(a[i] < b[i]) return fushu?'>':'<'; } return '='; } return fushu?'>':'<'; } };
8.实现标准string的数据转换成int 型对应的数据程序运行结果截图如下
函数文档说明如下
// function 15: make string(>0) into standard int number // input: 一个字符串 a,里面放的是一个整数; // output: 返回一个字符串,字符串里是a对应的整形数据; // 功能: 将存在字符串里的整数取出来,放在整形容器里,然后返回,根据返回的结果可以判定是否转换成功
算法思路代码实现如下// make string(>0) into standard int number std::pair<bool,int> String::String_into_intNumber(string &a) { if(Standardization(a)) { string max = Int_To_String(numeric_limits<int>::max()-1); bool fushu = false; if(a[0] == '-') { fushu = true ; a = a.substr(1,a.length()); } if(Compare(a,max) != '<') { cout<<"溢出 exception"<<endl; return std::make_pair(false,0); } int result = 0 ; for(size_t i =0;i<a.length();i++) { result = result * 10 + CharToNumber(a[i]); } if(fushu) result = - result; return std::make_pair(true,result); } else { cout<<"exception of function String_into_intNumber input"<<endl; return std::make_pair(false,0); } };over
-
总的代码
有的函数过于简单,故没有一一列出,小的函数在下面我派生的类里,代码如下
#include <iostream> #include <string> #include <limits> using namespace std; // extra the class of string class String:public string { public: // function 1: mode the add of int( (-3) + (-3) ) = - 6 // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相加操作,结果存在返回的字符串里 static string ADD_Int(string a,string b); // function 2: make a-b mode int a - b; 7 - (-3) = 10 // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相减操作,结果存在返回的字符串里 static string MINUS_Int(string a,string b); // function 3: make a*b mode int a * b; // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相乘操作,结果存在返回的字符串里 static string MULT_Int(string a,string b); // function 4: mode the division a/b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的相除操作,结果存在返回的字符串里 static string DIV_Int(string a,string b); // function 5: pow number a^b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符串,字符串里面是整数; // 功能: 实现参数两个整数的a^b操作,结果存在返回的字符串里 static string Pow_Int(string a,string b); // function 6: int To string :"123" = 123 // input: 一个int数 a; // output: 返回一个字符串,字符串里面是整数; // 功能: 将整数a转换成对应的字符串格式 static string Int_To_String(int x); // function 7: static char division a/b : 4 / 3 static string Division(string a,string b); // function 8: make a-b mode int a - b; 4 - 3 static string MinusInt(string a,string b); // function 9: mode the add of int :3 + 4 static string AddInt(string a,string b); // function 10: make char to the int number :'9' = 9 static int CharToNumber(char c); // function 11: make int to the model char : 7 = '7' static string IntToChar(int i); // function 12: check whether the string is legal static bool check_all_number(string a); // function 13: compare string a and b // input: 两个字符串 a 和 b,里面放的都是整数; // output: 返回一个字符,字符里是a和b的大小关系; // 功能: 实现参数两个整数的a和b比较操作,结果< or = or >存在返回的字符里 static char Compare(string a,string b); // function 14: make string into standard string number static bool Standardization(string &a); // function 15: make string(>0) into standard int number // input: 一个字符串 a,里面放的是一个整数; // output: 返回一个字符串,字符串里是a对应的整形数据; // 功能: 将存在字符串里的整数取出来,放在整形容器里,然后返回,根据返回的结果可以判定是否转换成功 static std::pair<bool,int> String_into_intNumber(string &a); }; // mode the add of int string String::ADD_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input ADD_Int"; } Standardization(a); Standardization(b); if(a[0] != '-' && b[0] != '-') return AddInt(a,b); else if(a[0] != '-'&& b[0] == '-') return MinusInt( a,b.substr( 1,b.size() ) ); else if(a[0] == '-'&& b[0] != '-') return MinusInt(b,a.substr(1,a.size())); else return '-'+AddInt(a.substr(1,a.size()),b.substr( 1,b.size() )); }; // make a-b mode int a - b; string String::MINUS_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input Multiplies_Int"; } Standardization(a); Standardization(b); if(a[0] != '-' && b[0] != '-') return MinusInt(a,b); else if(a[0] != '-' && b[0] == '-') return AddInt(a,b.substr(1,b.size())); else if(a[0] == '-' && b[0] != '-') return "-"+AddInt(a.substr(1,a.size()),b); else return MinusInt( b.substr(1,b.size()) , a.substr(1,a.size()) ); }; // make a*b mode int a * b; string String::MULT_Int(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input Multiplies_Int"; } Standardization(a); Standardization(b); string::size_type i = a.size(),j = b.size(); string c = "0",d = ""; bool fushu = (a[0] == '-' && b[0] != '-')||(a[0] != '-' && b[0] == '-'); if(a[0] == '-') a = a.substr(1,a.size()); if(b[0] == '-') b = b.substr(1,b.size()); int jinwei = 0; for( j = b.size()-1 ; j < b.size() ;j--) { // each number of b to * a jinwei = 0; for( i = a.size()-1 ; i < a.size() ;i-- ) { d = IntToChar( ( CharToNumber(a[i]) * CharToNumber(b[j]) + jinwei ) % 10 )+ d ; jinwei = ( CharToNumber(a[i]) * CharToNumber(b[j]) + jinwei ) / 10 ; } if(jinwei) d = IntToChar(jinwei) +d; // add all number result c = ADD_Int(c,d); d = ""; unsigned int zero = 0 ; while( zero < b.size() - j ) { d = d + '0'; zero ++; } } Standardization(c); if( fushu && c != "0" ) return '-'+c; else return c; }; // mode the division a/b string String::DIV_Int(string a,string b) { // exception of input if( a.empty() ) return "0"; else if( b.empty() ) return "e"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input DIV_Int"; } Standardization(a); Standardization(b); if(b == "0") return "e"; bool fushu = (a[0] == '-' && b[0] != '-')||(a[0] != '-' && b[0] == '-'); if( a[0] == '-' ) a = a.substr(1,a.size()); if( b[0] == '-' ) b = b.substr(1,b.size()); if( Compare(a,b) == '<' ) return "0"; string yushu = ""; string beichushu = a.substr(0,b.size()); string shang = Division( beichushu , b); yushu = MinusInt( beichushu ,MULT_Int( shang, b) ); string c = shang; for(string::size_type i = b.size(); i<a.size(); i++) { beichushu = yushu+ a[i] ; shang = Division( beichushu , b); c = c + shang; yushu = MinusInt( beichushu ,MULT_Int( shang, b) ); } Standardization(c); return fushu?('-'+c):c; }; // function: pow number x,y string String::Pow_Int(string a,string b) { // exception of input if( a.empty() ) return "0"; else if( b.empty() ) return "e"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input DIV_Int"; } Standardization(a); Standardization(b); string result = "1" ; if(Compare(b,"0") != '<') for(string i ="0" ;Compare(i,b) == '<' ;i = AddInt(i,"1")) { result = MULT_Int(result,a); } else for(string i ="0" ;Compare(i,b) == '>' ;i = MINUS_Int(i,"1")) { result = DIV_Int(result,a); } return result ; }; // function : int To string string String::Int_To_String(int x) { bool fushu = false; string result=""; if(x < 0 ) { fushu = true ; x = -x; } else if( x == 0 ) return "0"; while(x) { result = IntToChar(x % 10) + result; x = x/10; } if(fushu) result = "-"+result; return result; }; // static char division a/b string String::Division(string a,string b) { // exception of input if( a.empty() ) return "0"; else if( b.empty() ) return "e"; if(!check_all_number(a) || !check_all_number(b)) { cout<<"exception of input Division"<<endl; return "e"; } Standardization(a); Standardization(b); int i = 0; while( i<=9 ) { // if a - b*i < b if( Compare( MINUS_Int( a , MULT_Int(IntToChar(i),b) ) , b ) == '<' ) break; i++; } if( i>9 ) return "e"; return ""+IntToChar(i); }; // make a-b mode int a - b; string String::MinusInt(string a,string b) { // exception of input if(!check_all_number(a) || !check_all_number(b)) return "exception of input MinusInt"; Standardization(a); Standardization(b); // particular string of input if(a.empty()) { if(b.empty()) return "0"; else return "-"+b; } else if(b.empty()) { return a; } // normal number a < b string c = ""; bool check = true ; if(Compare(a,b) == '=') return "0"; else if(Compare(a,b) == '<') { c = a ; a = b ; b = c ; c = ""; check = false ; } // normal number a >= b string::size_type i = a.size()-1, j = b.size()-1; int jiewei = 0,now; while(i < a.size() && j < b.size()) { now = CharToNumber(a[i]) - CharToNumber(b[j]) - jiewei ; if( now < 0 ) { jiewei = 1; now = 10 + now ; } else jiewei = 0; c = IntToChar(now) + c ; i--;j--; } while(i < a.size()) { now = CharToNumber(a[i]) - jiewei ; if( now < 0 ) { jiewei = 1; now = 10 + now ; } else jiewei = 0; c = IntToChar( now ) + c ; i--; } Standardization(c); if(!check) c = '-' + c; return c; }; // mode the add of int string String::AddInt(string a,string b) { // exception of input if( a.empty() ) return b; else if( b.empty() ) return "0"; if(!check_all_number(a) || !check_all_number(b)) { return "exception of input AddInt"; } Standardization(a); Standardization(b); string::size_type i = a.size()-1 ,j = b.size()-1 , k = 0 ; string c = ""; int jinwei = 0; while( i < a.size() && j < b.size() ) { c = IntToChar( ( CharToNumber(a[i]) + CharToNumber(b[j]) + jinwei ) % 10 ) + c; jinwei = ( CharToNumber(a[i]) + CharToNumber(b[j]) + jinwei ) / 10; j--;i--; } while( j < b.size() ) { c = IntToChar( ( CharToNumber(b[j]) + jinwei ) % 10 ) + c; jinwei = ( jinwei + CharToNumber(b[j]) ) / 10; j--; } while( i < a.size() ) { c = IntToChar( ( CharToNumber(a[i]) + jinwei ) % 10 ) + c; jinwei = ( jinwei + CharToNumber(a[i]) ) / 10; i--; } if( jinwei ) c = IntToChar( jinwei ) + c; Standardization(c); return c; }; // make char to the int number int String::CharToNumber(char c) { if( c >= '0' && c <= '9' ) return int(c - '0'); else { cout<<c<<" exception of input CharToNumber "<<endl; system("pause"); return 0; } }; // make int to the model char string String::IntToChar(int i) { if( i >= 0 && i <= 9 ) { string c = ""; return c+char(i+48); } else { cout<<i<<" exception of input IntToChar"<<endl; system("pause"); return "e"; } }; // check whether the string is legal bool String::check_all_number(string a) { if(a.empty()) return true ; string::size_type L = a.size(),i = 0; if(a[0] == '-') i++; while( i < L ) { if( a[i] < '0' || a[i] > '9') return false; i++; } return true ; }; // compare string a and b char String::Compare(string a,string b) { if(a.empty() || b.empty()) { cout<<"error of input compare"; return 'e'; } else { if(!check_all_number(a) || !check_all_number(b)) { return 'e'; } Standardization(a); Standardization(b); if(a[0] == '-' && b[0] != '-') return '<'; else if( a[0] != '-' && b[0] == '-') return '>'; bool fushu = (a[0] == '-'); if(a.size() > b.size() ) return fushu?'<':'>'; else if(a.size() == b.size()) { for(string::size_type i = 0;i < a.size(); i++) { if(a[i] > b[i]) return fushu?'<':'>'; if(a[i] < b[i]) return fushu?'>':'<'; } return '='; } return fushu?'>':'<'; } }; // make string into standard string number bool String::Standardization(string &a) { if(!check_all_number(a)) { cout<<a<<" exception of input Standardization"<<endl; return false; } string::size_type i = 0; bool fushu = false ; if( a[0] == '-' ) { fushu = true; i = 1; } while(i < a.size()) { if(a[i] != '0') break; i++; } if(i == a.size()) i--; a = a.substr(i,a.size()); if( fushu && a != "0") a = '-' + a; return true ; }; // make string(>0) into standard int number std::pair<bool,int> String::String_into_intNumber(string &a) { if(Standardization(a)) { string max = Int_To_String(numeric_limits<int>::max()-1); bool fushu = false; if(a[0] == '-') { fushu = true ; a = a.substr(1,a.length()); } if(Compare(a,max) != '<') { cout<<"溢出 exception"<<endl; return std::make_pair(false,0); } int result = 0 ; for(size_t i =0;i<a.length();i++) { result = result * 10 + CharToNumber(a[i]); } if(fushu) result = - result; return std::make_pair(true,result); } else { cout<<"exception of function String_into_intNumber input"<<endl; return std::make_pair(false,0); } };