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

}
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;
}
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 removeHeadZero(Node* &head){
    while(head != NULL && head->data=='0') {
        head = head->next;
    }
    if(head == NULL){
        addHeadChar(head, '0');
    }
}
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(head1 == NULL) return head2;
    if(head2 == NULL) 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');
    }
    removeHeadZero(result);
    return result;
}

Node* sub(Node* head1, Node* head2)
{
    if(head1 == NULL) {
        addHeadChar(head2, '-');
        return head2;
    }
    if(head2 == NULL) 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;
    }

    removeHeadZero(result);
    if(isNegative) addHeadChar(result, '-');
    return result;
}
void appendZero(Node* &head, int n){ // n for how many zeros to add
    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;
    }
    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');
        removeHeadZero(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));
    //displayList(head1L);
    //displayList(head1R);
    //displayList(head2L);
    //displayList(head2R);

    Node* x1 = mult(head1L, head2L);
    //cout<<"x1: ";displayList(x1);
    Node* x2 = mult(head1R, head2R);
    //cout<<"x2: ";displayList(x2);
    Node* x3 = mult(add(head1L, head1R), add(head2L, head2R));
    //cout<<"x3: ";displayList(x3);
    Node* first = x1;
    appendZero(first, n);
    //cout<<"first: ";
    //displayList(first);

    Node* second = sub(x3, add(x1, x2));
    //cout<<"second: ";
    //displayList(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;
}
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+(BigDecimal& b1){
    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+(double& b1){
    BigDecimal d = BigDecimal(b1);
    return (*this+d);
}
BigDecimal operator+(double b, BigDecimal& b1){
    BigDecimal d = BigDecimal(b);
    return d+b1;
}

BigDecimal BigDecimal::operator-(BigDecimal& b1){
    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 = 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-(double& b1){
    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){
    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)) || (!isPositive(head1) && isPositive(head2))) {
        isNegative = true;
    }
    removeSign(head1);
    removeSign(head2);
    removeDot(head1);
    removeDot(head2);
    result = mult(head1, head2);

    if(isNegative) addHeadChar(result, '-');
    ret.linkedList = result;
    return ret;
}
BigDecimal BigDecimal::operator*(double& b1){
    BigDecimal d = BigDecimal(b1);
    return (*this)*d;
}
BigDecimal operator*(double b, BigDecimal& b1){
    BigDecimal d = BigDecimal(b);
    return d*b1;
}

BigDecimal BigDecimal::operator/(BigDecimal& b1){
}
BigDecimal BigDecimal::operator/(double& b1){
    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& BigDecimal::operator=(double& d){
}
BigDecimal& BigDecimal::operator=( int& i){
}
BigDecimal& BigDecimal::operator=( float& f){
}

BigDecimal& BigDecimal::operator++(){
}
BigDecimal BigDecimal::operator++(int i){
}

BigDecimal& BigDecimal::operator--(){
}
BigDecimal BigDecimal::operator--(int i){
}
bool BigDecimal::operator>( BigDecimal& b1){
}
bool BigDecimal::operator>( double& b1){
}
bool BigDecimal::operator>( int& b1){
}
bool BigDecimal::operator>( float& b1){
}

bool BigDecimal::operator>=( BigDecimal& b1){
}
bool BigDecimal::operator>=( double& b1){
}
bool BigDecimal::operator>=( int& b1){
}
bool BigDecimal::operator>=( float& b1){
}

bool BigDecimal::operator<( BigDecimal& b1){
}
bool BigDecimal::operator<( double& b1){
}
bool BigDecimal::operator<( int& b1){
}

bool BigDecimal::operator<( float& b1){
}

bool BigDecimal::operator<=( BigDecimal& b1){
}
bool BigDecimal::operator<=( double& b1){
}
bool BigDecimal::operator<=( int& b1){
}
bool BigDecimal::operator<=( float& b1){
}

bool BigDecimal::operator==( BigDecimal& b1){
}
bool BigDecimal::operator==( double& b1){
}
bool BigDecimal::operator==( int& b1){
}
bool BigDecimal::operator==( float& b1){
}

bool BigDecimal::operator!=( BigDecimal& b1){
}
bool BigDecimal::operator!=( double& b1){
}
bool BigDecimal::operator!=( int& b1){
}
bool BigDecimal::operator!=( float& b1){
}

BigDecimal BigDecimal::operator^( BigDecimal& b){
}

istream& BigDecimal::operator>>(BigDecimal& b){
}
ostream& BigDecimal::operator<<(const BigDecimal& b){
}