코딩 문제1: 큰 숫자 계산 (arithmatic operation with very big number)

//given basic add,sub,mul,div function. 

// the problems ask to calculate any math operation till required precision like 20th decimal point.

//since float type have limit to represent this kind of precision, number should be converted to decimal point only at last stage. during intermediate stage number should be represented as vulgar fraction. and number input is string type to handle big numbers.

// for example, 2000 * 49 + 67 - 45/ 6 * 7 is problems, it should be converted A/B form 

// by using vulgar faction calculation method. multiply and divide have precedence than adding subtraction.

// solution should use dynamic program method, divide big problems to smaller multiple problems. and smallest problems return fraction to upper level.

//upper level do fraction operation with returned number and return result again to upper level.

//final level should have one vulgar fraction number without losing precision. and covert it to decimal fraction at last point. below answer not include fraction to decimal number converting logic. almost took 8Hours for me.

//the main time consuming part isn't coding, coming up idea that it need to use vulgar fraction representation intermediate stages, consume most of time due to  trial&error attempt.

#include "stdafx.h"

#include <iostream>

#include <string>

using namespace std;

#define MAX_NUMBERLEN (20)

#define MAX_STRLEN (MAX_NUMBERLEN + 1)

#define MAX_TMPLEN (MAX_NUMBERLEN * 2)

#define MAX_T (2)

//basic given functions. below is just for basic test. not included in problems.

//these function should be extended to handle big number which over long long type limit.

void add(char *rst, char* a, char*b)

{

    long long lhs = stoll(a);

    long long rhs = stoll(b);

    long long rs = lhs + rhs;

    strcpy_s(rst,MAX_STRLEN, to_string(rs).c_str());

}

void sub(char *rst, char* a, char*b)

{

    long long lhs = stoll(a);

    long long rhs = stoll(b);

    long long rs = lhs - rhs;

    strcpy_s(rst,MAX_STRLEN, to_string(rs).c_str());

}

void mul(char *rst, char* a, char*b)

{

    long long lhs = stoll(a);

    long long rhs = stoll(b);

    long long rs = lhs * rhs;

    strcpy_s(rst,MAX_STRLEN, to_string(rs).c_str());

}

void div(char *rst, char* a, char*b)

{

    long long lhs = stoll(a);

    long long rhs = stoll(b);

    long long rs = lhs / rhs;

    strcpy_s(rst,MAX_STRLEN, to_string(rs).c_str());

}

///----------------------------------

struct fractionNo {

    char no[MAX_STRLEN];

    char deno[MAX_STRLEN];

    fractionNo() :no{ "0" }, deno{ "1" } {};

    fractionNo(char* in) : deno{ "1" } {

        if (in) {

            strcpy_s(no,MAX_STRLEN, in);

        }

        else {

            strcpy_s(no,MAX_STRLEN, "0");

        }

    };

    void strcpy_check(char *des, char *src) {

        if (MAX_NUMBERLEN < strlen(src)) {

            cout << "overflow = " << src << endl;

        }

        else {

            strcpy_s(des,MAX_STRLEN, src);

        }

    }

    //rhs will be changed. should not be used after operation.

    fractionNo &operator+(fractionNo &rhs) {

        

        char tmp[MAX_TMPLEN] {}; 

        mul(tmp, no, rhs.deno);

        strcpy_check(no, tmp);

        mul(tmp, rhs.no, deno);

        strcpy_check(rhs.no, tmp);

        add(tmp, no, rhs.no);

        strcpy_check(no, tmp);

        mul(tmp, rhs.deno, deno);

        strcpy_check(deno, tmp);

        return *this;

    }

    fractionNo &operator-(fractionNo &rhs) {

        char tmp[MAX_TMPLEN] {}; 

        mul(tmp, no, rhs.deno);

        strcpy_check(no, tmp);

        mul(tmp, rhs.no, deno);

        strcpy_check(rhs.no, tmp);

        sub(tmp, no, rhs.no);

        strcpy_check(no, tmp);

        mul(tmp, rhs.deno, deno);

        strcpy_check(deno, tmp);

        return *this;

    }

    fractionNo &operator*(fractionNo &rhs) {

        char tmp[MAX_TMPLEN] {}; 

        mul(tmp, rhs.deno, deno);

        strcpy_check(deno, tmp);

        mul(tmp, no, rhs.no);

        strcpy_check(no, tmp);

        return *this;

    }

    fractionNo &operator/(fractionNo &rhs) {

        char tmp[MAX_TMPLEN] {}; 

        mul(tmp, rhs.deno, no);

        strcpy_check(no, tmp);

        mul(tmp, deno, rhs.no);

        strcpy_check(deno, tmp);

        return *this;

    }

};

std::ostream & operator<<(ostream& out, const fractionNo &in) {

    out << "(" << in.no << "/" << in.deno <<")";

    return out;

}

#define OP_ADD (0)

#define OP_SUB (1)

#define OP_MUL (2)

#define OP_DIV (3)

#define OP_MAX (4)

int divideIn(char *lhs, char ** rhs)

{

    int locs[OP_MAX]{ 0 }; //?

    int len = strlen(lhs);

    for(int i = 0; i < len; i++) {

        switch (lhs[i]) {

        case '+':

            locs[OP_ADD] = i;

            break;

        case '-':

            locs[OP_SUB] = i;

            break;

        case '*':

            locs[OP_MUL] = i;

            break;

        case '/':

            locs[OP_DIV] = i;

            break;

        default:

            break;

        }

    }

    for (int i = 0; i < OP_MAX; i++) {

        if (locs[i] != 0) {

            auto loc = locs[i];

            lhs[loc++] = '\0';

            *rhs = &lhs[loc];

            return i;

        }

    }

    cout << "number =" << lhs << endl;

    return OP_MAX;

}

fractionNo calculate(char *in)

{

    char * newin = nullptr;

    auto ret = divideIn(in, &newin);

    if (OP_MAX == ret) {

        //this is leaf. this is just number without operator

        return fractionNo(in);

    }

    

    cout <<"Before:" << "lhs=" << in << ", rhs=" << newin << endl;

    auto lhs = calculate(in);

    auto rhs = calculate(newin);

    cout <<"After:" << "lhs=" << lhs << ", rhs=" << rhs << endl;

    switch (ret) {

    case OP_ADD:

        return (lhs + rhs);

    case OP_SUB:

        return (lhs - rhs);

    case OP_MUL:

        return (lhs * rhs);

    case OP_DIV:

        return (lhs / rhs);

    };

}

void run(char *rst, char *in)

{

    auto ret = calculate(in);

    cout <<"Final:"<< ret << endl;

    //convert fraction to decimal, missing here

}

int main()

{

    int t = MAX_T;

    char in[MAX_T][MAX_STRLEN];

    char rst[MAX_STRLEN];

    strcpy_s(in[0],MAX_STRLEN, "40235/45+547-37*60");

    strcpy_s(in[1],MAX_STRLEN, "-45+35/2");

    while (0 < t--) {

        run(rst, in[t]);

        //cout << rst;

    }

    return 0;

}