I'm being hard in the problem about implement linked list over very large interger and operator connected with it. Please hellp me!
I have implemented it follow
- I created two class is digitList (perform a positive interger, of course, not perform a negative interger) and Interger class (perform a negative interger)and its prototype in detail as follow
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
|
class digitList
{
public:
int digit;
digitList* nextDigit;
public:
digitList():digit(0), nextDigit(NULL){}
digitList(int d, digitList *next):digit(d), nextDigit(next){}
int getDigit(){
return digit;
}
digitList* getNextDigit(){
return nextDigit;
}
digitList* copy(){
if(nextDigit == NULL)
return new digitList(digit, NULL);
else
return new digitList(digit, nextDigit->copy());
}
int length()
{
if(nextDigit == NULL)
return 1;
else
return 1 + nextDigit->length();
}
digitList* leftDigits(int n)
{
if(n <= 0) return NULL;
else if(nextDigit == NULL) return new digitList(digit, NULL);
else return new digitList(digit, nextDigit->leftDigits(n-1));
}
digitList* rightDigits(int n)
{
if(n <= 0) return NULL;
else if(length() <= n) return NULL;
else
{
digitList* pTemp;
pTemp = this;
for(int i = 0; i<length() - n; i++)
pTemp = pTemp->getNextDigit();
digitList* pHead = NULL;
digitList* pTail = NULL;
digitList* node;
while(pTemp != NULL)
{
node = new digitList();
node->digit = pTemp->getDigit();
node->nextDigit = NULL;
if(pHead == NULL)
{
pHead = node;
pTail = node;
}
else
{
pTail->nextDigit = node;
pTail = node;
}
pTemp = pTemp->getNextDigit();
}
return pHead;
}
}
};
class Integer
{
public :
digitList* digits;
int sign;
public:
~Integer(){}
Integer(): sign(1), digits(NULL){}
Integer(digitList *L): sign(1), digits(L) {}
Integer(int i, digitList *L):sign(sgn(i)), digits(L) {}
Integer(int i): sign(sgn(i)), digits(digitize(abs(i))) { }
Integer(char str[])
{
if(str[0] == '-')
{
sign = -1;
for(int i = 0; i<strlen(str)-1; i++)
str[i] = str[i+1];
str[strlen(str)-1] = '\0';
digits = digitize(str);
}
else
{
sign = 1;
digits = digitize(str);
}
}
int length()
{
if (digits == NULL)
return 0;
else
return digits->length();
}
Integer copy()
{
if(digits == NULL)
return Integer(0);
else
return Integer(sign, digits->copy());
}
int sgn(int i)
{
if(i < 0) return -1;
else return 1;
}
};
| |
I have implemented some prototype such as
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
|
Integer trimDigit() //remove zero numbers at last list, means at head's interger.
{
return Integer(sign, trimDigitList(digits));
}
Integer operator +(Integer L);
Integer operator -(Integer L);
Integer leftDigits(int n); // return a list contain n last element in the left
Integer rightDigits(int n);//return a list contain n first element in the right
Integer shift(int n); // shift integer n position
Integer operator *(Integer L);
};
Integer computeValue(int operatorNum);
digitList *digitize(char str[80]);
digitList *digitize(char str[80])
{
digitList* L = 0;
digitList* node;
int i;
for(i = 0; i< strlen(str); i++)
{
if(str[i] < '0' || str[i] > '9') break;
node = new digitList(str[i] - '0', L);
L = node;
}
return L;
}
digitList *digitize(int n);//change a interger into a digitList's name
{
if(n == 0)
return NULL;
else
return new digitList(n % radix, digitize(n / radix));
}
int compareDigitLists(digitList* L1, digitList* L2)
//compare two integer is performed as L1 and L2,with L1 and L2 in a digitList
form.return 0 if L1=L2,1 if L1>L2 and -1 if L1<L2
{
// L1 == L2 : return 0
// L1 > L2 : return 1
// L1 < L2 : return -1
if((L1 == NULL) && (L2 == NULL)) return 0;
else if(L1 == NULL) return -1;
else if(L2 == NULL) return 1;
else
{
switch(compareDigitLists(L1->getNextDigit(), L2->getNextDigit()))
{
case 1: return 1;
case -1: return -1;
case 0:
if(L1->getDigit() > L2->getDigit())
return 1;
else if(L1->getDigit() == L2->getDigit())
return 0;
else
return -1;
}
}
}
digitList* addDigitLists(int c, digitList* L1, digitList* L2)
//plus two list,parameter c to get a carry value
{
if((L1 == NULL) && (L2 == NULL)) return digitize(c);
else if(L1 == NULL) return addDigitLists(c, L2, NULL);
else if(L2 == NULL)
{
int t = c + L1->getDigit();
return new digitList(t % radix, addDigitLists( t / radix, L1->getNextDigit(), NULL));
}
else
{
int t = c + L1->getDigit() + L2->getDigit();
return new digitList(t % radix, addDigitLists( t / radix, L1->getNextDigit(), L2->getNextDigit()));
}
}
| |
Input data in program to be contain in file input.txt has some information:
- line 1 show that the file has how many operand.
- line 2 to 2+n one line contain one operand
- line n-1 subsequent line one line contain one operator
and computing don't consider to the prior.
Exam:
3
123456
12345
1234
+
-
Result is ((123456+12345)-1234)
Note: operand contain numbers from 0 to 9, also able contain exponent(^) or factorial (!).
Help me implement some other prototype
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
|
digitList *trimDigitList(digitList* L); //remove zero numbers at last list.
digitList *subDigitLists(int b, digitList* L1, digitList* L2);
//minus two list together
Integer Integer::operator +(Integer L)
// implement plus operator, it now only execute over same intergers
Integer Integer::operator +(Integer L)
{
if(sign == L.sign)
return Integer(sign, addDigitLists(0, digits, L.digits));
}
Integer Integer::operator -(Integer L)
// implement minus operator
Integer Integer::operator *(Integer Y)// implement multiply operator
It was separated into
-Integer Integer::leftDigits(int n)
-Integer Integer:: rightDigits (int n)
-Integer Integer:: shift (int n) //execute multiply with 10^n
Integer computeValue(int operatorNum)
// complete program computing step by step.
{
Integer L1, L2;
L1 = operandArr[0];
for(int i = 0; i<operatorNum; i++)
{
L2 = operandArr[i+1];
switch(operatorArr[i])
{
case '+':
L1 = L1 + L2;
break;
}
}
return L1;
}
digitList *digitize(char str[80])//allow to read both exponent(^) and factorial(!)
| |
(Small note:I intend execute multiply operator follow recursion method as
x ×y= (xleft+ 10^n*xright) × (yleft+ 10^n*yright) = xleft× yleft + 10^n*(xright× yleft + xleft× yright) + 10^2n(xright× yright)
That's really so funny. Please help me and discuss together to complete great problem.
Thank you...
(If you have anything what don't understand or query, Please let me question)
