BigInteger类型的解析_傻瓜版_傻瓜都能看懂

  1 /*9876543210987654234522345
  2 214748364723453452323452345
  3 2147483647234523452323452345
  4 181760911432744962345234523
  5 2345234523434656346345634563测试数据*/
  6 #include<iostream>
  7 #include<cstdlib>
  8 #include<cstring>
  9 #include<iterator>
 10 #include<set>
 11 #include<vector>
 12 #include<map>
 13 #include<utility>
 14 #include<algorithm>
 15 #include<queue> 
 16 using namespace std;
 17 
 18 struct BigInteger {
 19     static const int BASE = 100000000;    //静态成员变量---属于BigInteger这个类型的，不属于他的结构体变量 
 20     static const int WIDTH = 8;           
 21     vector<int> s;                        //储存大整数 
 22     
 23     BigInteger(long long num = 0) {       //构造函数（带默认值) 
 24         *this = num;
 25     }
 26     BigInteger operator = (long long num) {//面对不超过long long的整数 
 27         s.clear();                         //清空本对象的vector容器内容--以免有上一次数据影响 
 28         //将整数里面的数八位八位的 储存到 vector里面去 
 29         do {
 30             s.push_back(num % BASE);      //假如整数是9位--得到了后面的八位 
 31             num /= BASE;                  //继续得到前面的位数 
 32         } while (num > 0);
 33         return *this;                     //返回本对象 
 34     }
 35     //long long类型不够的情况 
 36     BigInteger operator = (const string& str) { //赋值运算符 
 37         s.clear(); 
 38         int x, len = (str.length() - 1) / WIDTH + 1; //有几个八位一组(多出来的不足8位舍去) 
 39         //从右向左8位8位的储存整数到vector<int>中 
 40         for (int i = 0; i < len; i++) {              //按一共有几组八位储存 
 41             int end = str.length() - i*WIDTH;        //i个八位一组--字符串长度 - 几个八位 = 前面剩余的位数
 42             //取max(0,前面位数 - 8个长度),如果该剩余位数不为0,就取大的
 43             int start = max(0,end-WIDTH);
 44             //成为查找一组数的开始位置，如果取的是end-WIDTH,,那么end-start = WIDTH得到了一个八位,当做查找字符串的长度
 45             //sscanf()是将字符以某种形式取出存放到相应的类型中(这里是int),substr(start--开始搜寻的位置(包括),
 46             //end-start----是代表搜寻的长度),c_str()返回一个指针指向字符串相当于一个‘\0‘结尾的字符数组->用来终止一次 
 47             //8位的取出到x 
 48             sscanf(str.substr(start,end-start).c_str(), "%d", &x);
 49             //要注意在最高位前面的几组8位中，如果他们的第八位为0，那么组成整数的时候就不会有八位，输出时要注意 
 50             s.push_back(x); //将取出的整数push到vector的底部---大数是从右往左的一点点储存进去 
 51         }
 52         return *this;
 53     }
 54     //重载 + 运算符
 55     BigInteger operator + (const BigInteger& b) const
 56     {
 57         BigInteger c;
 58         c.s.clear();                 //清空c类型中vector内的元素 
 59         for (unsigned int i = 0, g = 0; ; i++)
 60         {
 61             if (g == 0 && i >= s.size() && i >= b.s.size())//如果位数已经到了最高位,i大于本对象对象且大于b对象的大小 
 62                 break;                                       //跳出循环 
 63             int x = g;
 64             if (i < s.size()) x += s[i];      
 65             if (i < b.s.size()) x += b.s[i];
 66             c.s.push_back(x % BASE);          //八位八位的取出取出后(从右向左)
 67             g = x/BASE;                       //得到最高位向后的位数(一直到从右向左出现的第一次8位前面停止) 
 68         }
 69         return c;    
 70     } 
 71 
 72     BigInteger operator += (const BigInteger &b)
 73     {
 74         *this = *this + b;
 75         return *this;
 76     }
 77     
 78 
 79     //比较运算符
 80     bool operator < (const BigInteger &b) const 
 81     {
 82         if (s.size() != b.s.size())
 83             return s.size() < b.s.size();
 84         for (int i = s.size() - 1; i >= 0; i--)    //从后往前面比较，因为(低位在vector的前面)注:这样做的前提是两个 
 85         {                                          //都没有前导0，否则不能比较 
 86             if (s[i] != b.s[i])    
 87                 return s[i] < b.s[i];
 88         }
 89         return false;                              //相等    
 90     }
 91     bool operator > (const BigInteger &b) const
 92     {
 93         return b < *this;
 94     }
 95     bool operator <= (const BigInteger &b) const
 96     {
 97         return !(b < *this);                    //相当于返回 本对象 <= b对象    
 98     }
 99     bool operator >= (const BigInteger &b) const
100     {
101         return !(*this < b);    
102     }  
103     bool operator != (const BigInteger &b) const
104     {
105         return b < *this || *this < b;
106     }
107     bool operator == (const BigInteger &b) const
108     {
109         return !(b < *this) || !(*this <  b);
110     }
111 };
112 
113 ostream& operator << (ostream &out, const BigInteger &x)
114 { 
115     out << x.s.back();            //从右向左输出(因为最高位是最后储存进去的)
116     //八位八位的写 
117     for (int i = x.s.size()-2; i >= 0; i--) {  //从倒数第二位开始输出 
118         char buf[20]; 
119         sprintf(buf, "%08d", x.s[i]);          //将整数当成字符写到buf中输出，不足八位的补零(因为在前面的几组八位中
120         //如果不足八位说明在形成整数的过程中最高位为0) 
121         for (unsigned int j = 0; j < strlen(buf); j++)  //输出八位 
122             out << buf[j];
123     }
124     return out; 
125 } 
126 
127 istream& operator >> (istream &in, BigInteger &x) {
128     string s;
129     if (! (in >> s)) 
130         return in;
131     x = s;              //输入正确的流 
132     return in;
133 } 
134 
135 struct cmp {
136     bool operator () (const BigInteger &a, const BigInteger &b) const {    //升序比较 
137         return a < b; 
138     }
139 };
140 
141 struct cmpL{
142     bool operator () (const BigInteger &a, const BigInteger &b) const {    //降序比较 
143         return a > b;
144     }
145 };
146 int main(void)
147 {
148     BigInteger bi, sum1, mus, b2;
149     
150     set<BigInteger,cmp> s1;
151     
152     vector<BigInteger> s2;
153     
154     map<BigInteger,char,cmpL> s3; 
155     
156     pair<BigInteger,char> s4;
157     
158     string ss; 
159     int i = 1;
160     
161     /*while (cin >> b2)        //利用了重载 >> 提取运算符 
162     {
163         mus += b2;    
164     }
165     cout << mus << endl;*/
166     
167     while (cin >> ss)
168     {
169         bi = ss;
170         sum1 += bi;
171         s1.insert(bi);
172         s2.push_back(bi);
173         s4.first = bi;
174         s4.second = ‘a‘+i;
175         i++;
176         s3.insert(s4);
177         
178     }
179     
180     for (set<BigInteger,cmp>::iterator it = s1.begin(); it != s1.end(); ++it) //set升序 
181         cout << *it << endl;
182 //    cout << sum1 << endl;
183     cout << endl;
184     
185     sort(s2.begin(),s2.end(),cmpL());       //sort 降序 
186     for (vector<BigInteger>::iterator it = s2.begin(); it != s2.end(); ++it)
187         cout << *it << endl;
188     
189     for (map<BigInteger,char,cmpL>::iterator it = s3.begin(); it != s3.end(); ++it) //map降序 
190         cout << (*it).second << endl;
191     return 0;
192 }