An integer class with high precision support using strings

HugeInt.cpp

// test2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
#include <string>	// 用字符串来表示HugeInt，方便输出

using namespace std;

// HugeInt的每一位
struct HugeIntDigit
{
	int data;			// 每一位可取 0 ~ 9，用int表示
	HugeIntDigit* next;	// 更高一位
	HugeIntDigit* front;	// 更低一位

	HugeIntDigit() {
		next = NULL;
		front = NULL;
		data = 0;
	}
};

typedef const HugeIntDigit* CONST_LPDIGIT;

class HugeIntList
{
	HugeIntDigit* head;
	int bit_count;

public:
	HugeIntList() {
		head = new HugeIntDigit;
		head->next = head;
		head->front = head;
		bit_count = 0;
	}
	~HugeIntList() {
		Clean();
	}
	void PushBack(int new_digit) {
		HugeIntDigit* pNewDigit = new HugeIntDigit;
		pNewDigit->data = new_digit;
		pNewDigit->front = head->front;
		head->front->next = pNewDigit;
		head->front = pNewDigit;
		pNewDigit->next = head;
		bit_count++;
	}
	void PushFront(int new_digit) {
		HugeIntDigit* pNewDigit = new HugeIntDigit;
		pNewDigit->data = new_digit;
		pNewDigit->next = head->next;
		head->next->front = pNewDigit;
		head->next = pNewDigit;
		pNewDigit->front = head;
		bit_count++;
	}
	int GetDigitCount() const { return bit_count; }
	const HugeIntDigit* Begin() const { return head->next; }
	const HugeIntDigit* End() const { return head; }
	const HugeIntDigit* rBegin() const { return head->front; }
	const HugeIntDigit* rEnd() const { return head; }

	// 直接返回指针将可以修改链表值，这两个函数仅为了使用乘法方便
	HugeIntDigit* mutable_begin() { return head->next; }
	HugeIntDigit* mutable_end() { return head; }

	void Clean() {
		HugeIntDigit* p = head->next;
		while (p != head) {
			HugeIntDigit* old_p = p;
			p = p->next;			
			old_p->front->next = old_p->next;
			old_p->next->front = old_p->front;
			delete old_p;
		}
		bit_count = 0;
	}
};

//declare the class of HugeInt
class HugeInt
{
	// 构造函数
public:
	HugeInt();
	HugeInt(int lNum); // 使用一个普通int构造HugeInt 默认值为0
	HugeInt(const char *szNum);	// 使用一个形如"12345...67890"的超大字符串构造HugeInt

	// 拷贝构造函数
	HugeInt(const HugeInt &other);	// 使用另一个HugeInt来复制出一个HugeInt对象

	// 赋值
	HugeInt& operator=(const HugeInt& other);	// 把other的值赋予本HugeInt

	// 计算操作
	HugeInt operator+(const HugeInt& other) const;   // 加上一个HugeInt
	HugeInt operator-(const HugeInt& other) const;	 // 减去一个HugeInt
	HugeInt operator*(const HugeInt& other) const;   // 乘以一个HugeInt

	// 比较操作
	bool	operator<(const HugeInt& other) const;	// 是否比other值小
	bool	operator==(const HugeInt& other) const;	// 是否与other相等
	bool	operator>(const HugeInt& other) const;	// 是否比other值大

	const char*	ToString();	// 把HugeInt的值用字符串表示出来

private:
	HugeIntList m_data;
	std::string m_str;
	bool	m_negative;	// 是否为负数
};

HugeInt::HugeInt() {
	m_negative = false;
}

HugeInt::HugeInt(int lNum)
{
	int s = 0;	// 绝对值
	if (lNum < 0) {	// lNum为负数
		s = -lNum;
		m_negative = true;
	} else {
		s = lNum;
		m_negative = false;
	}

	if (0 == s) {	// 待转换的整数为0
		m_data.PushBack(0);
		return;
	}

	// 挨个取出s每一位的值，添加到HugeInt对应的list里
	int remain = s % 10;	// 余数
	while (remain != 0) {
		m_data.PushBack(remain);
		s /= 10;
		remain = s % 10;
	}	
}

HugeInt::HugeInt(const char *szNum)
{
	int pos = 0;
	if ('-' == szNum[pos]) {	// 负数
		m_negative = true;
		pos++;
	} else if ('+' == szNum[pos]) {	// 正数
		m_negative = false;
		pos++;	
	} else {	// 没有标明，默认为正数
		m_negative = false;
	}
	while (szNum[pos] == '0'){	// 跳过前面多个连续的0
		pos++;
	}
	for  ( ; szNum[pos] != '\0'; pos++) {
		m_data.PushFront(szNum[pos] - '0');	// 因为字符串从高位开始数起，每次取出一位要加到链表最前
	}
}

//拷贝构造函数
HugeInt::HugeInt(const HugeInt &other)
{
	// 挨个遍历other的每一位，加到自己的bit链表最后
	for (const HugeIntDigit* pDigit = other.m_data.Begin(); pDigit != other.m_data.End(); pDigit = pDigit->next) {
		m_data.PushBack(pDigit->data);
	}
	m_negative = other.m_negative;
}

HugeInt& HugeInt::operator =(const HugeInt &other) {
	m_data.Clean();
	// 挨个遍历other的每一位，加到自己的bit链表最后
	for (const HugeIntDigit* pDigit = other.m_data.Begin(); pDigit != other.m_data.End(); pDigit = pDigit->next) {
		m_data.PushBack(pDigit->data);
	}
	m_negative = other.m_negative;
	return (*this);
}

HugeInt HugeInt::operator +(const HugeInt& other) const
{
	// 异号整数相加，将后者变号，再做同号减法
	if (m_negative != other.m_negative) {
		HugeInt inverse(other);
		inverse.m_negative = !(inverse.m_negative);
		return ((*this) - inverse);
	}

	HugeInt sum;	// 返回值
	sum.m_negative = m_negative;

	const HugeIntDigit* p1 = m_data.Begin();			// 取出自己的个位数
	const HugeIntDigit* p2 = other.m_data.Begin();	// 取出other的个位数

	int add_up = 0;	// 保存进位
	while (p1 !=  m_data.End() && p2 != other.m_data.End()) {
		int n = p1->data + p2->data + add_up;	// 两位相加，加上进位
		add_up = n / 10;
		n = n % 10;
		sum.m_data.PushBack(n);
		p1 = p1->next;
		p2 = p2->next;
	}

	while (p1 != m_data.End()) {	// 如果自己还有没加完的高位
		int n = p1->data + add_up;
		add_up = n / 10;
		n = n % 10;
		sum.m_data.PushBack(n);
		p1 = p1->next;
	}

	while (p2 != other.m_data.End()) {	// 如果other还有没加完的高位
		int n = p2->data + add_up;
		add_up = n / 10;
		n = n % 10;
		sum.m_data.PushBack(n);
		p2 = p2->next;
	}

	// 自己和other相等，并且最高位需要进位
	if (add_up > 0) {
		sum.m_data.PushBack(add_up);
	}

	return sum;
}

bool HugeInt::operator <(const HugeInt &other) const {
	// 负数一定小于正数
	if (m_negative && !(other.m_negative)) {
		return true;
	}
	if (!m_negative && other.m_negative) {
		return false;
	}
	if (m_data.GetDigitCount() > other.m_data.GetDigitCount())	// 位数大的，负数则小，正数则大
		return m_negative;
	if (m_data.GetDigitCount() < other.m_data.GetDigitCount())	// 位数小的，正数则小，负数则大
		return (!m_negative);
	
	// 符号相同，位数也相同，从最高位挨个比较
	const HugeIntDigit* p1 = m_data.rBegin();
	const HugeIntDigit* p2 = other.m_data.rBegin();
	while (p1 != m_data.rEnd() && p2 != other.m_data.rEnd()) {
		if (p1->data < p2->data)	// 最高位小，正数则小负数则大
			return !m_negative;
		if (p1->data > p2->data)	// 最高位大，正数则大负数则小
			return m_negative;

		p1 = p1->next;
		p2 = p2->next;
	}

	return false;	// 相等
}

bool HugeInt::operator ==(const HugeInt &other) const {
	if (m_negative == other.m_negative) {	// 符号相同
		const HugeIntDigit* p1 = m_data.Begin();
		const HugeIntDigit* p2 = other.m_data.Begin();
		while (p1 != m_data.End() && p2 != other.m_data.End()) {
			if (p1->data != p2->data)
				return false;
			p1 = p1->next;
			p2 = p2->next;
		}
		if (p1 == m_data.End() && p2 == other.m_data.End()) {
			return true;
		}
	}
	return false;
}

bool HugeInt::operator >(const HugeInt& other) const {
	// 正数大于负数
	if (m_negative && !(other.m_negative)) {
		return false;
	}
	if (!m_negative && other.m_negative) {
		return true;
	}

	if (m_data.GetDigitCount() > other.m_data.GetDigitCount())	// 位数大的，负数则小，正数则大
		return !m_negative;
	if (m_data.GetDigitCount() < other.m_data.GetDigitCount())	// 位数小的，正数则小，负数则大
		return m_negative;
	
	// 符号相同，位数也相同，从最高位挨个比较
	const HugeIntDigit* p1 = m_data.rBegin();
	const HugeIntDigit* p2 = other.m_data.rBegin();
	while (p1 != m_data.rEnd() && p2 != other.m_data.rEnd()) {
		// p1, p2分别为当前最高位
		if (p1->data < p2->data)	// 最高位小，正数则小负数则大
			return m_negative;
		if (p1->data > p2->data)	// 最高位大，正数则大负数则小
			return !m_negative;
	}

	return false;	// 相等
}

HugeInt HugeInt::operator -(const HugeInt& other) const
{
	// 异号整数相减，将后者变号，再做同号加法
	if (m_negative != other.m_negative) {	// 负-正
		HugeInt inverse(other);
		inverse.m_negative = !(inverse.m_negative);
		return ((*this) + inverse);
	}

	if (*this == other) {
		return 0;
	}

	HugeInt val;	// 返回值
	const HugeIntDigit* p1 = NULL;
	const HugeIntDigit* p1end = NULL;
	const HugeIntDigit* p2 = NULL;
	const HugeIntDigit* p2end = NULL;
	if ((*this) > other) {
		val.m_negative = false;
		if (m_negative) {	// 大负-小负
			p1 = other.m_data.Begin();
			p1end = other.m_data.End();
			p2 = m_data.Begin();
			p2end = m_data.End();
		} else {	// 大正数-小正数
			p1 = m_data.Begin();
			p1end = m_data.End();
			p2 = other.m_data.Begin();
			p2end = other.m_data.End();
		}
	} else {
		val.m_negative = true;
		if (m_negative) {	// 小负-大负
			p1 = m_data.Begin();
			p1end = m_data.End();
			p2 = other.m_data.Begin();
			p2end = other.m_data.End();
		} else {	// 小正数-大正数
			p1 = other.m_data.Begin();
			p1end = other.m_data.End();
			p2 = m_data.Begin();
			p2end = m_data.End();
		}
	}

	int borrow = 0;	// 借位
	while (p1 != p1end && p2 != p2end) {
		HugeIntDigit* pDigit = new HugeIntDigit;
		int n = p1->data - borrow - p2->data;
		if (n >= 0) {
			borrow = 0;
		} else {
			borrow = 1;
			n += 10;
		}
		val.m_data.PushBack(n);
		val.ToString();

		p1 = p1->next;
		p2 = p2->next;
	}

	while (p1 != p1end) {
		int n = p1->data - borrow;
		if (n >= 0) {
			borrow = 0;
		} else {
			borrow = 1;
			n += 10;
		}
		val.m_data.PushBack(n);

		p1 = p1->next;
	}

	return val;
}

HugeInt HugeInt::operator *(const HugeInt& other) const {
	HugeInt res;
	if (m_negative == other.m_negative) {	// 同号相乘为正
		res.m_negative = false;
	} else {
		res.m_negative = true;
	}

	const HugeIntDigit* p1 = m_data.Begin();	// 自己是被乘数
	const HugeIntDigit* p1end = m_data.End();
	const HugeIntDigit* p2 = other.m_data.Begin();	// other是乘数
	const HugeIntDigit* p2end = other.m_data.End();

	// 记录结果与当前乘数对应的前一位，例如当前用乘数的第2位做乘法，则此指针指向计算结果的第1位
	HugeIntDigit* p_start = res.m_data.mutable_begin();	
	HugeIntDigit* p = p_start;	// 记录乘的结果应该加在已有结果的哪一位上

	int mul_up = 0;	// 乘法进位
		
	while (p2 != p2end) {
		p = p_start->next;	// 加在下一位上
		while (p1 != p1end) {
			int n = p2->data * p1->data + mul_up;
			mul_up = n / 10;
			n = n % 10;
			if (p == res.m_data.mutable_end()) {
				res.m_data.PushBack(n);
			} else {	// 该位已存在
				n += p->data;	// 加上已有的值
				mul_up += n / 10;	// 增加新的进位
				n = n % 10;		// 该位的新值
				p->data = n;
				p = p->next;
			}
			p1 = p1->next;
		}
		while (mul_up > 0) {	// 如果还有没有进位没有加上
			int n = mul_up;
			mul_up = n / 10;
			n = n % 10;
			if (p == res.m_data.mutable_end()) {
				res.m_data.PushBack(n);
			} else { // 该位已经存在
				n += p->data;
				mul_up += n / 10;
				n = n % 10;
				p->data = n;
				p = p->next;
			}
		}
		p2 = p2->next;	// 取出乘数的高一位
		p_start = p_start->next;	// 对应地应该加在高一位上
		p1 = m_data.Begin();	// 被乘数重新从最低位开始
	}

	return res;
}

const char* HugeInt::ToString()
{
	const HugeIntDigit* pDigit = m_data.rBegin();
	while (pDigit != m_data.rEnd() && 0 == pDigit->data) {	// 跳过前导多个0
		pDigit = pDigit->front;
	}
	if (pDigit == m_data.rEnd()) {	// 已经到最后了，即这个数字只有多个0组成
		m_negative = false;	// 强制改为正数
		m_str.assign("0");
		return m_str.c_str();
	}

	m_str.clear();
	if (m_negative)
		m_str.append("-");	// 加上负号

	char temp_str[2] = { '0', '\0' };
	while (pDigit != m_data.rEnd()) {
		temp_str[0] = pDigit->data + '0';
		m_str.append(temp_str);	// 把数字转换为字符串
		pDigit = pDigit->front;
	}

	return m_str.c_str();
}


int main() {
	cout << "Input the arithmetic formular: (like 1 + 2, -12 - -5, 0 * 999)" << endl;
	string s1, s2;
	char op;
	cin >> s1 >> op >> s2;

	HugeInt h1(s1.c_str());
	HugeInt h2(s2.c_str());
	HugeInt result;

	cout << h1.ToString() << endl;
	cout << h2.ToString() << endl;

	switch (op) {
		case '+':
			result = h1 + h2;
			break;
		case '-':
			result = h1 - h2;
			break;
		case '*':
			result = h1 * h2;
			break;
		default:
			cout << "Input error, calculation failed." << endl;
			return -1;
	}

	cout << s1 << " " << op << " " << s2 << " = " << result.ToString() << endl;

	return 0;	
}