fork(1) download 
  1. #include <iostream>
  2. #include <list>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. class Bigint {
  8. public:
  9.     static Bigint fromString(const string& strint);
  10. 	string toString() const;
  11. 	Bigint add(const Bigint& bigint) const;
  12. 	Bigint subtract(const Bigint& bigint) const;
  13. protected:
  14. 	int sign;
  15. 	list<int> digs;
  16. 	Bigint(const int& sign, const list<int>& digs);
  17. 	static list<int> pad(const list<int>& digs, const int& len);
  18. 	static list<int> trim(const list<int>& digs);
  19. 	static int compare(const list<int>& digs1, const list<int>& digs2);
  20. 	static list<int> add(const list<int>& digs1, const list<int>& digs2);
  21. 	static list<int> subtract(const list<int>& digs1, const list<int>& digs2);
  22. };
  23.  
  24. Bigint Bigint::fromString(const string& strint) {
  25. 	int sign = 1;
  26. 	int i = 0;
  27. 	if (strint[0] == '+') {
  28. 		sign = 1;
  29. 		i = 1;
  30. 	}
  31. 	else if (strint[0] == '-') {
  32. 		sign = -1;
  33. 		i = 1;
  34. 	}
  35. 	list<int> digs;
  36. 	for (; i < strint.length(); i++) digs.push_back(int(strint[i] - '0'));
  37. 	return Bigint(sign, digs);
  38. }
  39.  
  40. string Bigint::toString() const {
  41. 	string result = "";
  42. 	if (this->sign < 0) result += '-';
  43. 	for (list<int>::const_iterator iter = this->digs.begin(); iter != this->digs.end(); iter++) 
  44. 		result += '0' + *iter;
  45. 	return result;
  46. }
  47.  
  48. Bigint Bigint::add(const Bigint& bigint) const {
  49. 	int sign;
  50. 	list<int> digs;
  51. 	list<int> digs1 = pad(this->digs, this->digs.size() < bigint.digs.size() ? bigint.digs.size() - this->digs.size() : 0);
  52. 	list<int> digs2 = pad(bigint.digs, bigint.digs.size() < this->digs.size() ? this->digs.size() - bigint.digs.size() : 0);
  53. 	if (this->sign == bigint.sign) {
  54. 		sign = this->sign;
  55. 		digs = add(digs1, digs2);
  56. 	}
  57. 	else {
  58. 		list<int>* greater_digs, * less_digs;
  59. 		int cmp_result = compare(digs1, digs2);
  60. 		if (cmp_result < 0) {
  61. 			less_digs = &digs1;
  62. 			greater_digs = &digs2;
  63. 			sign = bigint.sign;
  64. 		}
  65. 		else {
  66. 			greater_digs = &digs1;
  67. 			less_digs = &digs2;
  68. 			sign = cmp_result > 0 ? sign = this->sign : 1;
  69. 		}
  70. 		digs = trim(subtract(*greater_digs, *less_digs));
  71. 	}
  72. 	return Bigint(sign, digs);
  73. }
  74.  
  75. Bigint Bigint::subtract(const Bigint& bigint) const {
  76. 	return add(Bigint(-bigint.sign, bigint.digs));
  77. }
  78.  
  79. Bigint::Bigint(const int& sign, const list<int>& digs) : sign(sign), digs(digs) {}
  80.  
  81. list<int> Bigint::pad(const list<int>& digs, const int& len) {
  82. 	list<int> result;
  83. 	for (int i = 0; i < len; i++) result.push_back(int(0));
  84. 	result.insert(result.end(), digs.begin(), digs.end());
  85. 	return result;
  86. }
  87.  
  88. list<int> Bigint::trim(const list<int>& digs) {
  89. 	list<int> result;
  90. 	list<int>::const_iterator iter = digs.begin();
  91. 	while (iter != digs.end() && *iter == 0) iter++;
  92. 	if (iter == digs.end()) iter--;
  93. 	result.insert(result.end(), iter, digs.end());
  94. 	return result;
  95. }
  96.  
  97. int Bigint::compare(const list<int>& digs1, const list<int>& digs2) {
  98. 	int result = 0;
  99. 	list<int>::const_iterator iter1 = digs1.begin();
  100. 	list<int>::const_iterator iter2 = digs2.begin();
  101. 	while (iter1 != digs1.end()) {
  102. 		if (*iter1 == *iter2) {
  103. 			iter1++;
  104. 			iter2++;
  105. 			continue;
  106. 		}
  107. 		if (*iter1 < *iter2) result = -1;
  108. 		else if (*iter1 > *iter2) result = 1;
  109. 		break;
  110. 	}
  111. 	return result;
  112. }
  113.  
  114. list<int> Bigint::add(const list<int>& digs1, const list<int>& digs2) {
  115. 	list<int> result;
  116. 	list<int>::const_reverse_iterator iter1 = digs1.rbegin();
  117. 	list<int>::const_reverse_iterator iter2 = digs2.rbegin();
  118. 	bool carry_flag = false;
  119. 	while (iter1 != digs1.rend()) {
  120. 		int val = *iter1 + *iter2 + (carry_flag ? 1 : 0);
  121. 		carry_flag = val > 9;
  122. 		if (carry_flag) val -= 10;
  123. 		result.push_front(val);
  124. 		iter1++;
  125. 		iter2++;
  126. 	}
  127. 	if (carry_flag) result.push_front(1);
  128. 	return result;
  129. }
  130.  
  131. list<int> Bigint::subtract(const list<int>& digs1, const list<int>& digs2) {
  132. 	list<int> result;
  133. 	list<int>::const_reverse_iterator iter1 = digs1.rbegin();
  134. 	list<int>::const_reverse_iterator iter2 = digs2.rbegin();
  135. 	bool carry_flag = false;
  136. 	while (iter1 != digs1.rend()) {
  137. 		int val = *iter1 - *iter2 - (carry_flag ? 1 : 0);
  138. 		carry_flag = val < 0;
  139. 		if (carry_flag) val += 10;
  140. 		result.push_front(val);
  141. 		iter1++;
  142. 		iter2++;
  143. 	}
  144. 	return result;
  145. }
  146.  
  147. int main(void) {
  148. 	cout << Bigint::fromString("2134490128490823084023483024892").add(Bigint::fromString("60981690786891763458749732985")).toString() << endl;
  149. 	cout << Bigint::fromString("2134490128490823084023483024892").add(Bigint::fromString("-60981690786891763458749732985")).toString() << endl;
  150. 	cout << Bigint::fromString("-2134490128490823084023483024892").add(Bigint::fromString("60981690786891763458749732985")).toString() << endl;
  151. 	cout << Bigint::fromString("-2134490128490823084023483024892").add(Bigint::fromString("-60981690786891763458749732985")).toString() << endl;
  152. 	cout << Bigint::fromString("990").add(Bigint::fromString("900")).toString() << endl;
  153. 	cout << Bigint::fromString("990").add(Bigint::fromString("-900")).toString() << endl;
  154. 	cout << Bigint::fromString("-990").add(Bigint::fromString("900")).toString() << endl;
  155. 	cout << Bigint::fromString("-990").add(Bigint::fromString("-900")).toString() << endl;
  156. 	cout << Bigint::fromString("-123").subtract(Bigint::fromString("-3456")).toString() << endl;
  157. 	return 0;
  158. }
  159.  
Success #stdin #stdout 0s 2992KB
comments (?)
stdin 
Standard input is empty
stdout 
2195471819277714847482232757877
2073508437703931320564733291907
-2073508437703931320564733291907
-2195471819277714847482232757877
1890
90
-90
-1890
3333
https://ideone.com/EISNdg
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!