qq.cpp

#include "bigDecimal.h"
#include <iostream>
#include <sstream>
#include <stack>
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 lenBigDecimal(const Node* head1)
{
    int len1 = 0;
    while(head1 != NULL)
    {
        head1 = head1->next;
        len1++;
    }
    return len1;
}
bool maxFirst(Node* head1, Node* head2){
    int len1 = lenBigDecimal(head1);
    int len2 = lenBigDecimal(head2);
    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;
            }
            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;
    }
}

Node* positive_addition(Node* head1, Node* head2)
{
    // declare variables
    int diff = 0;
    int toAdd = 0, carry = 0, prevCarry = 0;

    // make the format consistent (no leading '+' sign)
    if(head1->data == '+') {
        head1 = head1->next;
    }
    if(head2->data == '+') {
        head2 = head2->next;
    }

    // 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;

    // first traverse the shorter list
    while(reverse2 != NULL){
        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');
    }
    return result;
}
void displayList(Node* head)
{
    while(head != NULL)
    {
        printf("%c", head->data);
        head = head->next;
    }
    printf("\n");
}

Node* positive_subtraction(Node* head1, Node* head2)
{
    // declare variables
    int sign = 1;
    int carry = 0, prevCarry = 0, toAdd = 0;

    // make the format consistent (no leading '+' sign)
    if(head1->data == '+') {
        head1 = head1->next;
    }
    if(head2->data == '+') {
        head2 = head2->next;
    }

    // make b1 the larger value
    if(!maxFirst(head1, head2)) {
        swapNode(head1, head2);
        sign*=-1;
    }

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

    while(reverse2 != NULL){
        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;
    }

    if(sign == -1) addHeadChar(result, '-');
    return result;
}

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;
    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 = positive_subtraction(list2, list1);
    }
    // - -
    else if(!isPositive(linkedList) && !isPositive(b1.linkedList)) {
        p = changeSign(positive_addition(list1, list2));
    }
    // + -
    else if(isPositive(linkedList) && !isPositive(b1.linkedList)) {
        p = positive_subtraction(list1, list2);
    }
    // + +
    else if(isPositive(linkedList) && isPositive(b1.linkedList)) {
        p = positive_addition(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(positive_addition(list1, list2));
    }
    // - - -> - +
    else if(!isPositive(linkedList) && !isPositive(b1.linkedList)) {
        p = positive_subtraction(list2, list1);
    }
    // + - -> + +
    else if(isPositive(linkedList) && !isPositive(b1.linkedList)) {
        p = positive_addition(list1, list2);
    }
    // + + -> + -
    else if(isPositive(linkedList) && isPositive(b1.linkedList)) {
        p = positive_subtraction(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 BigDecimal::operator*(double& b1){
}
//BigDecimal BigDecimal::operator*(const BigDecimal& b1);

BigDecimal BigDecimal::operator/(BigDecimal& b1){
}
BigDecimal BigDecimal::operator/( double& b1){
}
//BigDecimal BigDecimal::operator/(const BigDecimal& 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){
}