qqq.cpp

#include "bigDecimal.h"
#include <iostream>
#include <sstream>
#include <stack>
#include <math.h>
#include <cstring>
using namespace std;

// helper functions
bool isPositive(Node* b) {
	if (b->data == '-')
		return false;
	return true;
}
void addHeadChar(Node* &head, char c) {
	Node* p = new Node;
	p->data = c;
	p->next = head;
	head = p;
}
void swapNode(Node* &head1, Node* &head2) {
	Node* tmp = head1;
	head1 = head2;
	head2 = tmp;
}
Node* getReverse(Node* head) {
	Node* reverseList = NULL;
	Node* last = head;

	while (last != NULL) {
		addHeadChar(reverseList, last->data);
		last = last->next;
	}
	return reverseList;
}
Node* linkedListFromStr(string str, int length) {
	// init head
	Node* head = NULL;
	int i;
	for (i = 0; i < length; i++) {
		if (str[i] == '.')
			break;
	}
	if (length - i - 1 > 5) {
		for (int j = 5 + i; j >= 0; j--) {
			addHeadChar(head, str[j]);
		}
	} else {
		for (int j = length - 1; j >= 0; j--) {
			addHeadChar(head, str[j]);
		}
	}

	return head;
}
int len(const Node* head1, bool beforeDot) {
	int len1 = 0;
	int len2 = 0;
	while (head1 != NULL && head1->data != '.') {
		head1 = head1->next;
		len1++;
	}
	if (head1 != NULL && head1->data == '.')
		head1 = head1->next;
	while (head1 != NULL) {
		head1 = head1->next;
		len2++;
	}

	if (beforeDot)
		return len1;
	return len2;
}
void displayList(Node* head) {
	while (head != NULL) {
		cout << head->data;
		head = head->next;
	}
	cout << endl;
}
void fixLen(Node* &head, int n) {
	int len1 = len(head, 1);
	int diff = n - len1;
	while (diff--)
		addHeadChar(head, '0');
}
bool equalList(Node* head1, Node* head2) {
	int len11 = len(head1, 1);
	int len12 = len(head1, 0);
	int len21 = len(head2, 1);
	int len22 = len(head2, 0);
	if (len11 != len21 || len21 != len11)
		return false;
	while (head1 != NULL) {
		if (head1->data != head2->data)
			return false;
		head2 = head2->next;
		head1 = head1->next;
	}
	return true;
}
void removeSign(Node* &head) {
	if (head->data == '+' || head->data == '-')
		head = head->next;
}
bool maxFirst(Node* head1, Node* head2) {
	if (isPositive(head1) && !isPositive(head2))
		return true;
	if (!isPositive(head1) && isPositive(head2))
		return false;
	removeSign(head1);
	removeSign(head2);

	int len1 = len(head1, 1);
	int len2 = len(head2, 1);
	Node* last1 = head1;
	Node* last2 = head2;

	if (len1 < len2)
		return false;
	else if (len1 == len2) {
		while (last1 != NULL) {
			if (last1->data < last2->data)
				return false;
			if (last1->data > last2->data)
				return true;
			last1 = last1->next;
			last2 = last2->next;
		}
	}
	return true;

}
bool lessThan(Node* head1, Node* head2) {
	if (!maxFirst(head1, head2))
		return true;
	return false;
}
Node* changeSign(Node* head) {
	if (head->data == '-') {
		head = head->next;
		return head;
	} else {
		//if it is positive
		if (head->data == '+') {
			head = head->next;
		}
		addHeadChar(head, '-');
		return head;
	}
}
bool hasDot(Node* head) {
	while (head != NULL) {
		if (head->data == '.')
			return true;
		head = head->next;
	}
	return false;
}

void removeDot(Node* &head) {
	Node* last = head;
	Node* result = NULL;

	while (last != NULL) {
		if (last->data != '.') {
			addHeadChar(result, last->data);
		}
		last = last->next;
	}
	head = getReverse(result);
}
bool isZero(Node* head) {
	if (head == NULL)
		return true;
	removeSign(head);
	removeDot(head);
	while (head != NULL) {
		if (head->data != '0')
			return false;
		head = head->next;
	}
	return true;
}
void removeZero(Node* &head) {
	// remove head zeros
	while (head != NULL && head->data == '0') {
		head = head->next;
	}
	if (head == NULL) {
		addHeadChar(head, '0');
	}

	//remove tail zeros
	if (hasDot(head)) {
		Node* last = getReverse(head);
		while (last != NULL) {
			if (last->data == '0') {
				last = last->next;
			} else
				break;
		}
		// remove the dot if it is in the last position with no zeros behind
		if (last->data == '.')
			last = last->next;
		head = getReverse(last);
	}
}
void alignLen(Node* &head1, Node* &head2) {
	int len1 = len(head1, 1); // this is the length after the dot, cause the list passed in is reversed
	int len2 = len(head2, 1);
	if (!hasDot(head1))
		len1 = 0;
	if (!hasDot(head2))
		len2 = 0;

	int diff = 0;
	if (len1 < len2) {
		if (!hasDot(head1))
			addHeadChar(head1, '.');
		diff = len2 - len1;
		while (diff--)
			addHeadChar(head1, '0');
	} else if (len2 < len1) {
		if (!hasDot(head2))
			addHeadChar(head2, '.');
		diff = len1 - len2;
		while (diff--)
			addHeadChar(head2, '0');
	}
}

Node* add(Node* head1, Node* head2) {
	if (isZero(head1) && isZero(head2)) {
		Node* p = NULL;
		addHeadChar(p, '0');
		return p;
	}
	if (isZero(head1))
		return head2;
	if (isZero(head2))
		return head1;
	// declare variables
	int toAdd = 0, carry = 0, prevCarry = 0;

	// make the format consistent (no leading '+' sign)
	removeSign(head1);
	removeSign(head2);

	// let the first input length always > the second one
	if (!maxFirst(head1, head2))
		swapNode(head1, head2);

	Node* reverse1 = getReverse(head1);
	Node* reverse2 = getReverse(head2);
	Node* result = NULL;

	alignLen(reverse1, reverse2);

	// first traverse the shorter list
	while (reverse2 != NULL) {
		if (reverse2->data == '.') {
			addHeadChar(result, '.');
			reverse2 = reverse2->next;
			reverse1 = reverse1->next;
		}

		toAdd = (reverse1->data - '0') + (reverse2->data - '0') + prevCarry;
		if (toAdd > 9) {
			toAdd -= 10;
			carry = 1;
		}

		addHeadChar(result, toAdd + '0');

		reverse1 = reverse1->next;
		reverse2 = reverse2->next;
		prevCarry = carry;
		carry = 0;
	}
	while (reverse1 != NULL) {
		toAdd = (reverse1->data - '0') + prevCarry;
		if (toAdd > 9) {
			toAdd -= 10;
			carry = 1;
		}

		addHeadChar(result, toAdd + '0');

		reverse1 = reverse1->next;
		prevCarry = carry;
		carry = 0;
	}

	if (prevCarry) {
		addHeadChar(result, prevCarry + '0');
	}
	removeZero(result);
	return result;
}

Node* sub(Node* head1, Node* head2) {
	if (isZero(head1) && isZero(head2)) {
		Node* p = NULL;
		addHeadChar(p, '0');
		return p;
	}
	if (isZero(head1)) {
		addHeadChar(head2, '-');
		return head2;
	}
	if (isZero(head2))
		return head1;
	// declare variables
	bool isNegative = false;
	int carry = 0, prevCarry = 0, toAdd = 0;

	// make the format consistent (no leading '+' sign)
	removeSign(head1);
	removeSign(head2);

	// make b1 the larger value
	if (!maxFirst(head1, head2)) {
		swapNode(head1, head2);
		isNegative = true;
	}

	Node* reverse1 = getReverse(head1);
	Node* reverse2 = getReverse(head2);
	Node* result = NULL;

	alignLen(reverse1, reverse2);

	while (reverse2 != NULL) {
		if (reverse2->data == '.') {
			addHeadChar(result, '.');
			reverse2 = reverse2->next;
			reverse1 = reverse1->next;
		}

		toAdd = (reverse1->data - '0') - (reverse2->data - '0') - prevCarry;
		if (toAdd < 0) {
			toAdd += 10;
			carry = 1;
		}

		addHeadChar(result, toAdd + '0');

		reverse1 = reverse1->next;
		reverse2 = reverse2->next;
		prevCarry = carry;
		carry = 0;
	}
	while (reverse1 != NULL) {
		toAdd = (reverse1->data - '0') - prevCarry;
		if (toAdd < 0) {
			toAdd += 10;
			carry = 1;
		}

		addHeadChar(result, toAdd + '0');

		reverse1 = reverse1->next;
		prevCarry = carry;
		carry = 0;
	}

	removeZero(result);
	if (isNegative)
		addHeadChar(result, '-');
	if (result == NULL)
		addHeadChar(result, '0');
	return result;
}
void appendZero(Node* &head, int n) { // n for how many zeros to add
	if (head->data == '0')
		return;
	Node* last = head;
	last = getReverse(head);
	while (n--)
		addHeadChar(last, '0');
	head = getReverse(last);
}
Node* slice(Node* head, int start, int length) {
	int index = 0;
	Node* result = NULL;
	while (head != NULL) {
		if (start == index) {
			while (length--) {
				addHeadChar(result, head->data);
				head = head->next;
			}
			return getReverse(result);
		}
		index++;
		head = head->next;
	}
	addHeadChar(result, '0');
	return result;
}
Node* mult(Node* head1, Node* head2) {

	Node* result = NULL;
	if (isZero(head1) || isZero(head2)) {
		Node* p = NULL;
		addHeadChar(p, '0');
		return p;
	}
	int len1 = len(head1, 1) + len(head1, 0); // the total length - the dot
	int len2 = len(head2, 1) + len(head2, 0);
	int n = max(len1, len2);

	if (n == 1) {
		int toAdd = (head1->data - '0') * (head2->data - '0');
		addHeadChar(result, toAdd % 10 + '0');
		addHeadChar(result, toAdd / 10 + '0');
		removeZero(result);
		return result;
	}

	Node* head1R = slice(head1, len1 - (n / 2), n / 2);
	Node* head1L = slice(head1, 0, len1 - (n / 2));
	Node* head2R = slice(head2, len2 - (n / 2), n / 2);
	Node* head2L = slice(head2, 0, len2 - (n / 2));

	Node* x1 = mult(head1L, head2L);
	Node* x2 = mult(head1R, head2R);
	Node* x3 = mult(add(head1L, head1R), add(head2L, head2R));
	Node* first = x1;
	appendZero(first, n);

	Node* second = sub(x3, add(x1, x2));
	appendZero(second, n / 2);

	// return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;
	return add(add(first, second), x2);
}
void rounding(Node* &result, int maxPosition) {
	if (!hasDot(result))
		return;
	int diff = len(result, 0) - (maxPosition + 1);
	result = getReverse(result);
	if (diff > 0) {
		while (diff--)
			result = result->next;
	}
	if (result->data >= '5') {
		result = result->next;
		result->data = result->data + 1;
		while (result->data > '9') {
			result = result->next;
			result->data = result->data + 1;
		}
	} else
		result = result->next;

	result = getReverse(result);
}
BigDecimal::BigDecimal() {
	linkedList = new Node; // don't forget to new!!
	linkedList->data = '0';
	linkedList->next = NULL;
}
BigDecimal::BigDecimal(const string str) {
	linkedList = linkedListFromStr(str, str.length());
}
BigDecimal::BigDecimal(const char* str) {
	linkedList = linkedListFromStr(str, strlen(str));
}
BigDecimal::BigDecimal(int i) {
	stringstream ss;
	ss << i;
	string str = ss.str();

	linkedList = linkedListFromStr(str, str.length());
}
BigDecimal::BigDecimal(float f) {

	stringstream ss;
	ss << f;
	string str = ss.str();

	linkedList = linkedListFromStr(str, str.length());
}
BigDecimal::BigDecimal(double d) {
	stringstream ss;
	ss << d;
	string str = ss.str();

	linkedList = linkedListFromStr(str, str.length());
}
BigDecimal::BigDecimal(const BigDecimal& bi) {
    Node* head = bi.linkedList;
    linkedList = NULL;
    while(head != NULL){
        addHeadChar(linkedList, head->data);
        head = head->next;
    }
	linkedList = getReverse(linkedList);
}
BigDecimal::~BigDecimal() {
	delete linkedList;
}

/* #### You need to implement from_string(const char*) and to_string(char*) methods. #### */
/**
 * Method: void from_string(const char* str)
 * Description:
 * 		from_string method will read the number from str.
 * 		If str is valid, it will be parsed and stored into sign and storage, and then return true. Otherwise, false will be returned.
 */
bool BigDecimal::from_string(const char* str) {
// if the input string is invalid
	int i = 0, flag = 0;
	if (str[i] == '+' || str[i] == '-') {
		i++;
	}
	if (str[i] == '.')
		return false;

	while (i < strlen(str)) {
		if (str[i] == '+' || str[i] == '-')
			return false;
		if (str[i] == '.') {
			if (!flag)
				flag = 1;
			else {
				// dot can only appear once
				return false;
			}
			i++;
			continue;
		}
		if (!(str[i] >= '0' && str[i] <= '9'))
			return false;
		i++;
	}
	if (i == strlen(str) - 1) {
		linkedList = linkedListFromStr(str, strlen(str));
		return true;
	}
	return false;
}

/**
 * Method: void to_string(const char* str)
 * Description:
 * 		to_string method will output the current number to str.
 */
void BigDecimal::to_string(char* str) {
	Node* last = linkedList;
	memset(str, 0, strlen(str)); // clear this arr first!
	int i = 0;
	while (last != NULL) {
		if (last->data == '+') {
			last = last->next;
		}
		str[i++] = last->data;
		last = last->next;
	}
	str[i] = '\0';
}

/* #### Please add your overloading methods below. #### */
BigDecimal& BigDecimal::operator=(const BigDecimal& b) {
	Node* head = b.linkedList;
	linkedList = NULL;
	while (head != NULL) {
		addHeadChar(linkedList, head->data);
		head = head->next;
	}
	linkedList = getReverse(linkedList);

	return *this;
}
BigDecimal& BigDecimal::operator=(const double& d) {
	return *this = BigDecimal(d);
}
BigDecimal& BigDecimal::operator=(const int& i) {
	return *this = BigDecimal(i);
}
BigDecimal& BigDecimal::operator=(const float& f) {
	return *this = BigDecimal(f);
}

BigDecimal& BigDecimal::operator++() {
	return *this = *this + 1.0;
}

BigDecimal BigDecimal::operator++(int) {
	BigDecimal bd(*this);
	*this = *this + 1.0;
	return bd;
}

BigDecimal& BigDecimal::operator--() {
	return *this = *this - 1.0;
}
BigDecimal BigDecimal::operator--(int) {
	BigDecimal bd(*this);
	*this = *this - 1.0;
	return bd;
}
bool BigDecimal::operator>(BigDecimal& b1) {
	return maxFirst(linkedList, b1.linkedList)
			&& !equalList(linkedList, b1.linkedList);
}
bool BigDecimal::operator>(double& b1) {
	BigDecimal bd(b1);
	return *this > bd;
}
bool BigDecimal::operator>(int& b1) {
	BigDecimal bd(b1);
	return *this > bd;
}
bool BigDecimal::operator>(float& b1) {
	BigDecimal bd(b1);
	return *this > bd;
}

bool BigDecimal::operator>=(BigDecimal& b1) {
	return !(*this < b1);
}
bool BigDecimal::operator>=(double& b1) {
	return !(*this < b1);
}
bool BigDecimal::operator>=(int& b1) {
	return !(*this < b1);
}
bool BigDecimal::operator>=(float& b1) {
	return !(*this < b1);
}

bool BigDecimal::operator<(BigDecimal& b1) {
	return lessThan(linkedList, b1.linkedList);
}
bool BigDecimal::operator<(double& b1) {
	BigDecimal bd(b1);
	return *this < bd;
}
bool BigDecimal::operator<(int& b1) {
	BigDecimal bd(b1);
	return *this < bd;
}
bool BigDecimal::operator<(float& b1) {
	BigDecimal bd(b1);
	return *this < bd;
}

bool BigDecimal::operator<=(BigDecimal& b1) {
	return !(*this > b1);
}
bool BigDecimal::operator<=(double& b1) {
	return !(*this > b1);
}
bool BigDecimal::operator<=(int& b1) {
	return !(*this > b1);
}
bool BigDecimal::operator<=(float& b1) {
	return !(*this > b1);
}

bool BigDecimal::operator==(BigDecimal& b1) {
	return equalList(linkedList, b1.linkedList);
}
bool BigDecimal::operator==(double& b1) {
	BigDecimal bd = BigDecimal(b1);
	return *this == bd;
}
bool BigDecimal::operator==(int& b1) {
	BigDecimal bd = BigDecimal(b1);
	return *this == bd;
}
bool BigDecimal::operator==(float& b1) {
	BigDecimal bd = BigDecimal(b1);
	return *this == bd;
}

bool BigDecimal::operator!=(BigDecimal& b1) {
	return !(*this == b1);
}
bool BigDecimal::operator!=(double& b1) {
	return !(*this == b1);
}
bool BigDecimal::operator!=(int& b1) {
	return !(*this == b1);
}
bool BigDecimal::operator!=(float& b1) {
	return !(*this == b1);
}

BigDecimal::BigDecimal(Node* head) {
	linkedList = head;
}
BigDecimal BigDecimal::operator+(const BigDecimal& b1) const {
	BigDecimal ret;
	Node* p;
	Node* list1 = linkedList;
	Node* list2 = b1.linkedList;
	if (!isPositive(linkedList))
		list1 = changeSign(linkedList);
	if (!isPositive(b1.linkedList))
		list2 = changeSign(b1.linkedList);
// - +
	if (!isPositive(linkedList) && isPositive(b1.linkedList)) {
		p = sub(list2, list1);
	}
// - -
	else if (!isPositive(linkedList) && !isPositive(b1.linkedList)) {
		p = changeSign(add(list1, list2));
	}
// + -
	else if (isPositive(linkedList) && !isPositive(b1.linkedList)) {
		p = sub(list1, list2);
	}
// + +
	else if (isPositive(linkedList) && isPositive(b1.linkedList)) {
		p = add(list1, list2);
	}

	ret.linkedList = p;
	return ret;
}
BigDecimal BigDecimal::operator+(const double& b1) const {
	BigDecimal d = BigDecimal(b1);
	return *this + d;
}
BigDecimal operator+(double b, BigDecimal& b1) {
	BigDecimal d = BigDecimal(b);
	return d + b1;
}

BigDecimal BigDecimal::operator-(const BigDecimal& b1) const {
	BigDecimal ret;
	Node* p = NULL;
	Node* list1 = linkedList;
	Node* list2 = b1.linkedList;
	if (!isPositive(linkedList))
		list1 = changeSign(linkedList);
	if (!isPositive(b1.linkedList))
		list2 = changeSign(b1.linkedList);
// - + -> - -
	if (!isPositive(linkedList) && isPositive(b1.linkedList)) {
		p = changeSign(add(list1, list2));
	}
// - - -> - +
	else if (!isPositive(linkedList) && !isPositive(b1.linkedList)) {
		p = sub(list2, list1);
	}
// + - -> + +
	else if (isPositive(linkedList) && !isPositive(b1.linkedList)) {
		p = add(list1, list2);
	}
// + + -> + -
	else if (isPositive(linkedList) && isPositive(b1.linkedList)) {
		p = sub(list1, list2);
	}

	ret.linkedList = p;
	return ret;
}
BigDecimal BigDecimal::operator-(const double& b1) const {
	BigDecimal d = BigDecimal(b1);
	return (*this - d);
}
BigDecimal operator-(double b, BigDecimal& b1) {
	BigDecimal d = BigDecimal(b);
	return d - b1;
}
// reference: http://www.cburch.com/csbsju/cs/160/notes/31/1.html
BigDecimal BigDecimal::operator*(BigDecimal b1) const {

	BigDecimal ret;
	Node* head1 = linkedList;
	Node* head2 = b1.linkedList;
	Node* result = NULL;
	bool isNegative = false;
	if (isZero(head1) || isZero(head2))
		return BigDecimal("0");

// if the multiplication result is negative
	if (isPositive(head1) != isPositive(head2) && !isZero(head1)
			&& !isZero(head2)) {
		isNegative = true;
	}
	removeSign(head1);
	removeSign(head2);
	removeZero(head1);
	removeZero(head2);

//deal with dot...
	int lenAfterDot1 = len(head1, 0);
	int lenAfterDot2 = len(head2, 0);
	int maxPrecision = max(lenAfterDot1, lenAfterDot2);

	int totalDotLen = lenAfterDot1 + lenAfterDot2;
	removeDot(head1);
	removeDot(head2);

	int lenMax = max(len(head1, 1), len(head2, 1));
	int num1 = log(lenMax) / log(2);
	int powerTwoLen = pow(2, num1);
	if (powerTwoLen != lenMax) {
		num1++;
		powerTwoLen = pow(2, num1);
	}
	fixLen(head1, powerTwoLen);
	fixLen(head2, powerTwoLen);

	result = mult(head1, head2);
	int resultLen = len(result, 1);

// add dot at last
	if (totalDotLen) {
		Node* tmp = result;
		result = NULL;
		int index = 0;
		bool dotAdd = false;
		bool nonNegative = false;
		while (tmp != NULL) {
			if (index == resultLen - totalDotLen) {
				addHeadChar(result, '.');
				dotAdd = true;
			}
			if (!dotAdd && !nonNegative) {
				if (tmp->data != '0') {
					addHeadChar(result, tmp->data);
					nonNegative = true;
				}
			} else
				addHeadChar(result, tmp->data);

			tmp = tmp->next;
			index++;
		}
		// remove the dot if it is in the last position
		if (result->data == '.')
			result = result->next;
		result = getReverse(result);
		rounding(result, maxPrecision);
	}

	removeZero(result);
	if (result->data == '.')
		addHeadChar(result, '0');

	if (isNegative)
		addHeadChar(result, '-');

	ret.linkedList = result;
	return ret;
}
BigDecimal BigDecimal::operator*(const double& b1) const {
	BigDecimal d = BigDecimal(b1);
	return (*this) * d;
}
BigDecimal operator*(double b, BigDecimal& b1) {
	BigDecimal d = BigDecimal(b);
	return d * b1;
}
// reference: http://www.geeksforgeeks.org/divide-large-number-represented-string/
BigDecimal BigDecimal::operator/(BigDecimal b1) const {
	if (isZero(linkedList) || (lessThan(linkedList, b1.linkedList) && len(linkedList, 0)==0 && len(b1.linkedList, 0) ==0))
		return BigDecimal("0");
	BigDecimal ret;
	Node* num = linkedList;
	Node* divisor = b1.linkedList;
	Node* result = NULL;
	int index = 0, diff = 0;
	bool isNegative = false;

	if (isPositive(num) != isPositive(divisor) && !isZero(num)
			&& !isZero(divisor))
		isNegative = true;
	removeSign(num);
	removeSign(divisor);


//deal with dot...
	int lenAfterDot1 = len(num, 0);
	int lenAfterDot2 = len(divisor, 0);
	int maxPrecision = max(lenAfterDot1, lenAfterDot2);

	removeDot(num);
	removeDot(divisor);
	removeZero(num);
	removeZero(divisor);


	if (lenAfterDot1 > lenAfterDot2) {
		diff = lenAfterDot1 - lenAfterDot2;
		appendZero(divisor, diff);
	} else {
		diff = lenAfterDot2 - lenAfterDot1;
		appendZero(num, diff);
	}
	appendZero(num, maxPrecision);
	//displayList(num); displayList(divisor);

// find prefix of number larger than divisor
	int len1 = len(num, 1);
	Node* prefix = NULL;
	addHeadChar(prefix, num->data);
	while (lessThan(prefix, divisor)) {
		appendZero(prefix, 1);
		Node* p = NULL;
		num = num->next;
		addHeadChar(p, num->data);
		prefix = add(prefix, p);
		index++;
	}
	while (index < len1) {
		// find prefix/divisor
		Node* divisors = divisor;
		int q = 0;

		while (!lessThan(prefix, divisors)) { // prefix >= divisors
			divisors = add(divisors, divisor);
			q++;
		}
		divisors = sub(divisors, divisor);
		prefix = sub(prefix, divisors);

		appendZero(prefix, 1);
		Node* p = NULL;
		num = num->next;
		if (num != NULL) { // the last digit won't have to append one digit after it
			addHeadChar(p, num->data);
			prefix = add(prefix, p);
		}

		if (index == len1 - maxPrecision)
			addHeadChar(result, '.');
		addHeadChar(result, q + '0');
		index++;
	}
	//displayList(result);
	result = getReverse(result);
	if(result->data =='.') addHeadChar(result, '0');
	if(len(result, 0)>5){
		rounding(result, maxPrecision);
		removeZero(result);
	}

	if (isNegative)
		addHeadChar(result, '-');

	if (result == NULL) {
		addHeadChar(result, '0');
	}

	ret.linkedList = result;
	return ret;
}
BigDecimal BigDecimal::operator/(const double& b1) const {
	BigDecimal d = BigDecimal(b1);
	return (*this) / d;
}
BigDecimal operator/(double b, BigDecimal& b1) {
	BigDecimal d = BigDecimal(b);
	return d / b1;
}

BigDecimal BigDecimal::operator^(BigDecimal& b) {
	BigDecimal bd(*this);
	BigDecimal bd_base(bd);

	Node* head = b.linkedList;
	Node* result = NULL;
	while(head != NULL && head->data != '.'){
        addHeadChar(result, head->data);
        head = head->next;
	}
	result = getReverse(result);
	BigDecimal power(result);
	BigDecimal zero("0");

	power--;
	while (power>zero) {
		bd = bd * bd_base;
		power--;
	}
	return bd;
}

istream& operator>>(istream& in, BigDecimal& b) {
	char c;
	char* s;
	int i = 0;
	while (in >> c) {
		s[i++] = c;
	}
	b.from_string(s);
	return in;
}
ostream& operator<<(ostream& out, BigDecimal& b) {
	char* s;
	b.to_string(s);
	string str(s);
	out << str;
	return out;
}