-
Notifications
You must be signed in to change notification settings - Fork 1
/
BigIntegerParser.h
211 lines (169 loc) · 4.82 KB
/
BigIntegerParser.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
/**
* BigInteger Class
* Version 9.0
* S. M. Mahbub Murshed ([email protected])
*/
#ifndef BIGINTEGER_PARSER
#define BIGINTEGER_PARSER
#include <vector>
#include <string>
using namespace std;
#include "BigInteger.h"
#include "algorithms/BigIntegerUtil.h"
#include "algorithms/classic/CommonAlgorithms.h"
namespace BigMath
{
class BigIntegerParser
{
public:
static vector<DataT> Convert(ULong n)
{
string num = to_string(n);
return Parse(num.c_str()).GetInteger();
}
static Int FindRange(char const* num, Int& start, Int& end, bool& isNegative)
{
Int char_processed = start;
isNegative = false;
// Take care of the sign
if (num[start] == '-')
{
isNegative = true;
start++;
}
else if (num[start] == '+')
{
start++;
}
// Trim leading zeros
while(num[start] == '0')
{
start++;
}
// Find the end of the string
end = start;
while(num[end] >= '0' && num[end] <= '9' && num[end] != 0)
{
end++;
}
char_processed = end - char_processed;
end--;
return char_processed;
}
static BigInteger Parse(char const* num, Int* char_processed = 0)
{
return Parse(num, 0, char_processed);
}
static BigInteger Parse(char const* num, Int start, Int* char_processed = 0)
{
if(num == NULL || start < 0)
return BigInteger();
Int end;
bool isNegative;
Int processed = FindRange(num, start, end, isNegative);
if(char_processed != 0)
*char_processed = processed;
// If the resulting string is empty return 0
if (start > end)
return BigInteger();
vector<DataT> bigInt = ParseUnsigned(num, start, end);
return BigInteger(bigInt, isNegative);
}
static vector<DataT> ParseUnsigned(char const* num, Int start, Int end)
{
vector<DataT> bigIntB1 = ParseUnsignedBase10n(
num,
start,
end,
BigIntegerUtil::Base100M_Zeroes);
vector<DataT> bigIntB2 = CommonAlgorithms::ConvertBase(
bigIntB1,
BigIntegerUtil::Base100M,
BigInteger::Base());
return bigIntB2;
}
// Group by n, meaning 10^n base
static vector<DataT> ParseUnsignedBase10n(char const* num, Int start, Int end, SizeT digits)
{
vector<DataT> bigInt(end / digits + 1);
SizeT j = 0;
bool error = false;
while(end >= start)
{
DataT digit = 0;
DataT TEN = 1;
for (SizeT i = 0; i < digits && end >= start; i++, end--)
{
// Current digit
int d = num[end] - '0';
if(d < 0 || d > 9)
{
error = true;
break;
}
digit += TEN * d;
TEN *= 10;
}
bigInt[j++] = digit;
if(error) break;
}
BigIntegerUtil::TrimZeros(bigInt);
return bigInt;
}
// Converts the integer to a string representation
static string ToString(BigInteger const& bigInt)
{
return ToString(bigInt.GetInteger(), bigInt.IsNegative());
}
static string ToString(vector<DataT> const& bigInt, bool isNeg = false)
{
return ToString(bigInt, 0, bigInt.size() - 1, isNeg);
}
static string ToString(vector<DataT> const& bigInt, SizeT start, SizeT end, bool isNeg = false)
{
if(BigIntegerUtil::IsZero(bigInt, start, end))
{
return *new string("0");
}
vector<DataT> bigIntB2 = CommonAlgorithms::ConvertBase(
bigInt, start, end,
BigInteger::Base(),
BigIntegerUtil::Base100M);
Int len = (Int)bigIntB2.size() * BigIntegerUtil::Base100M_Zeroes + 2;
char* num = new char[len];
Int j = UnsignedBase10nToString(
bigIntB2, 0, bigIntB2.size() - 1,
BigIntegerUtil::Base100M_Zeroes,
num, len);
if(isNeg)
num[j--] = '-';
string converted(num + j + 1);
delete [] num;
return converted;
}
// Convert unsigned integer to base 10^n string
static Int UnsignedBase10nToString(vector<DataT> const& a, SizeT start, SizeT end, SizeT baseDigit, char *num, SizeT len)
{
Int j = len - 1;
num[j--] = 0;
// Trim zeros
while(end >= start && a[end] == 0)
end--;
for(Int i = start; i <= end; i++)
{
DataT n = a[i];
SizeT l = 0;
while(l++ < baseDigit)
{
num[j--] = (n % 10) + '0';
n /= 10;
}
}
// Trim zeros
while(num[j+1] == '0')
j++;
return j;
}
};
}
#endif