qq.cpp

#include "bigDecimal.h"
#include <iostream>
#include <sstream>
#include <stack>
#include <math.h>
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* BigDecimal::linkedListFromStr(const string str)
{
    // init head
    Node* head = NULL;
    for(int j=str.length()-1; j>=0; j--) addHeadChar(head, str[j]);
    return head;
}
Node* BigDecimal::linkedListFromChar(const char* str)
{
    //init head
    Node* head = NULL;
    for(int j=strlen(str)-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)
    {
        printf("%c", head->data);
        head = head->next;
    }
    printf("\n");
}
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 len1 = len(head1, 1) + len(head1, 0);
    int len2 = len(head2, 1) + len(head2, 0);
    if(len1 != len2) return false;
    while(head1 != NULL){
        if(head1->data != head2->data) return false;
        head2 = head2->next;
        head1 = head1->next;
    }
    return true;
}
bool maxFirst(Node* head1, Node* 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) && !equalList(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 removeSign(Node* &head){
    if(head->data=='+' || head->data=='-') head = head->next;
}
bool isZero(Node* head){
    if(head == NULL) return true;
    removeSign(head);
    while(head != NULL){
        if(head->data != '0') return false;
        head = head->next;
    }
    return true;
}
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);
}
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)){
        int nonZero = 0;
        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;
        }
        //displayList(reverse2);
        //displayList(reverse1);

        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(head1 == NULL || head2 == NULL) {
        addHeadChar(result, '0');
        return result;
    }
    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);
}


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

    linkedList = linkedListFromStr(str);
}
BigDecimal::BigDecimal(float f)
{
    stringstream ss;
    ss << f;
    string str = ss.str();

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

    linkedList = linkedListFromStr(str);
}
BigDecimal::BigDecimal(const BigDecimal& bi)
{
    linkedList = bi.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 = linkedListFromChar(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;
    }
}


/* #### Please add your overloading methods below. #### */
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*(const BigDecimal& b1) const{
    BigDecimal ret;
    Node* head1 = linkedList;
    Node* head2 = b1.linkedList;
    Node* result = NULL;
    bool isNegative = false;
    int diff = 0;

    // if the multiplication result is negative
    if(isPositive(head1) != isPositive(head2)) {
        isNegative = true;
    }
    removeSign(head1);
    removeSign(head2);
    int totalDotLen = len(head1, 0) + len(head2, 0);
    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;
        while(tmp != NULL){
            if(index == resultLen - totalDotLen) {
                addHeadChar(result, '.');
                dotAdd = true;
            }
            if(!(dotAdd && tmp->data=='0')) 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);
    }
    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/(const BigDecimal& b1) const{
    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)) isNegative = true;
    removeSign(num);
    removeSign(divisor);

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

    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);
        }

        //cout<<index<<" ";displayList(result);
        if(index == len1 - maxPrecision) addHeadChar(result, '.');
        addHeadChar(result, q+'0');
        index++;
    }
    if(hasDot(result)){
        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);
    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=(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){
    BigDecimal bd = BigDecimal(d);
    *this = bd;
    return *this;
}
BigDecimal& BigDecimal::operator=(const int& i){
    BigDecimal bd = BigDecimal(i);
    *this = bd;
    return *this;
}
BigDecimal& BigDecimal::operator=(const float& f){
    BigDecimal bd = BigDecimal(f);
    *this = bd;
    return *this;
}

BigDecimal& BigDecimal::operator++(){
    BigDecimal b = *this+1.0;
    Node* head = b.linkedList;
    linkedList = NULL;
    while(head != NULL){
        addHeadChar(linkedList, head->data);
        head = head->next;
    }
    linkedList = getReverse(linkedList);
    return *this;
}

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

BigDecimal& BigDecimal::operator--(){
    BigDecimal b = *this-1.0;
    Node* head = b.linkedList;
    linkedList = NULL;
    while(head != NULL){
        addHeadChar(linkedList, head->data);
        head = head->next;
    }
    linkedList = getReverse(linkedList);
    return *this;
}
BigDecimal BigDecimal::operator--(int){
    BigDecimal b = *this-1.0;
    return b;
}
bool BigDecimal::operator>( BigDecimal& b1){
    return maxFirst(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);
}

bool BigDecimal::operator<(BigDecimal& b1){
    return lessThan(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);
}

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^(BigDecimal& b){
    Node* head = NULL;
    Node* last = b.linkedList;
    if(hasDot(last)){
        while(last->data != '.'){
            addHeadChar(head, last->data);
            last = last->next;
        }
    }
    head = getReverse(head);
    BigDecimal power = BigDecimal(head);
    BigDecimal zero;
    while(power-- >zero){
        *this = (*this)*(*this);
    }
    return *this;
}

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 = NULL;
    b.to_string(s);
    int len1 = strlen(s);
    int i = 0;
    while(len1--) out << s[i++];
    return out;
}