C++实现高精度计算器 (大数的加减乘除)

对我们已知的能进行四则运算的数据类型,就算最长的长长整型也是拥有它的极限长度的,所以对于更大的数的四则运算,我们就要选择其他的类型进行接收,并定义适合它们的算法:

这个案例中建议选择,string类型数据去接收要计算的大数,再将其转成int型储存在动态容器vector中,可以方便的去实现我们这个案例

具体实现代码和算法都放在了下面,注释很详细。

实现效果:(测试懒得敲太多数,用小一点的数方便检测)C++实现高精度计算器 (大数的加减乘除)直接上代码:

   具体思路看注释:

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include<algorithm>
using namespace std;
class Compute
{
public:
    Compute() {};
    ~Compute() {};
    virtual void compute(string& strA, string& strB) = 0;
};
class Add : public Compute //这是加法类
{
public:
    virtual void compute(string& strA, string& strB) override;
};
void Add::compute(string& strA, string& strB)
{
    vector<int> a;   //第一个容器存放第一个数
    vector<int> b;   //第二个容器存放第二个数
    vector<int> sum; //和容器存放俩数之和

    int index = 0; //设置进位

    //首先将俩个数保存在容器中
    //并且是逆序保存  为了迎合容器的Pushback添加函数
    for (int i = strA.size() - 1; i >= 0; i--)
    {
        a.push_back(strA[i] - '0');
    }

    for (int i = strB.size() - 1; i >= 0; i--)
    {
        b.push_back(strB[i] - '0');
    }

    //然后开始加法算法,对两个数逐位相加
    //首先我们不管俩个数的长度大小,一直加到最短的那个数完全被加
    for (int i = 0; i < strA.size() && i < strB.size(); i++)
    {
        sum.push_back((a[i] + b[i] + index) % 10); //将逐位相加的结果储存在sum容器中
        index = (a[i] + b[i] + index) / 10;        //满10则进行进位
    }

    //然后开始考虑长度比较长的数的多余位置没有参加算法
    if (strA.size() > strB.size())
    {
        //这是A的长度比b大的情况,这时候已经计算到了b的长度位上
        for (int i = strB.size(); i < strA.size(); i++)
        {
            sum.push_back((index + a[i]) % 10);
            index = (a[i] + index) / 10;
        }
    }

    if (strB.size() > strA.size())
    {
        //这是B的长度比A大的情况,这时候已经计算到了a的长度位上
        for (int i = strA.size(); i < strB.size(); i++)
        {
            sum.push_back((index + b[i]) % 10);
            index = (index + b[i]) / 10;
        }
    }

    //计算完毕后判断进位  如果进位不为空那么还要往前进1
    if (index != 0)
    {
        sum.push_back(1);
        index = 0; //并且清空进位
    }

    //到这里已经完成加法算法
    //下面为输出代码

    //由于使用的容器较多,我选择使用迭代器输出sum  vector容器里的数据 即为最后的结果
    cout << strA << "+" << strB << "=";
    for (vector<int>::iterator it = sum.end() - 1; it >= sum.begin(); it--)
    {
        cout << *it;
        if (it == sum.begin())
        {
            break;
        }
    }
    cout << endl;

    //最后一步使用vector容器与自身交换  用来清空多余的无用内存
    vector<int>().swap(a);
    vector<int>().swap(b);
    vector<int>().swap(sum);
    //函数结束
}

class Sub : public Compute //这是减法类
{
public:
    virtual void compute(string& strA, string& strB) override;
    int Comparevector(vector<int>a, vector<int>b);//声明减法内置比较函数
};
void Sub::compute(string& strA, string& strB) //对基类计算函数进行重写
{
    vector<int> a;        //容器a存入第一个数据
    vector<int> b;        //容器b存入第二个数据
    vector<int> difvalue; //差值容器存入最后结果
    int lend = 0;         //定义借位数
                          //添加这一步是若两数相等则直接给结果,不需要经过算法;
    if (strA == strB)
    {
        difvalue.push_back(0);
        goto flag;
    }
    //因为减法运算还是从低位开始 那么我们还是 将数据倒序存入
    for (int i = strA.size() - 1; i >= 0; i--)
    {
        a.push_back(strA[i] - '0');
    }

    for (int i = strB.size() - 1; i >= 0; i--)
    {
        b.push_back(strB[i] - '0');
    }

    //下面开始减法算法
    //我选择使用绝对值算法 -> 首先放正负到一边,计算之前判断谁大谁小,保证永远使用大数减小数,最后再进行符号讨论;
    if (Comparevector(a, b) != 0)
    {
        //首先计算位数相同的地方
        for (int i = 0; i < strB.size(); i++)
        {
            if (a[i] < b[i])
            {
                for (int j = i + 1; j < strA.size(); j++)
                {
                    //向高位借位,如果高位不为0,则可以正常借到;
                    if (a[j] != 0)
                    {
                        lend = 1;
                        a[j] -= 1;
                        break;
                    } //如果高位为0,则向更高位借,0上有借位看为9;
                    else
                    {
                        a[j] = 9;
                    }
                }
                difvalue.push_back(lend * 10 + a[i] - b[i]);
                lend = 0;
            }
            else
            {
                difvalue.push_back(a[i] - b[i]);
            }
        }
        for (int i = strB.size(); i < strA.size(); i++)
        {
            difvalue.push_back(a[i]);
        }
    }
    else
    {
        //之后算法和之前相同
        //首先计算位数相同的地方
        for (int i = 0; i < strA.size(); i++)
        {
            if (b[i] < a[i])
            {
                for (int j = i + 1; j < strB.size(); j++)
                {
                    //向高位借位,如果高位不为0,则可以正常借到;
                    if (b[j] != 0)
                    {
                        lend = 1;
                        b[j] -= 1;
                        break;
                    } //如果高位为0,则向更高位借,0上有借位看为9;
                    else
                    {
                        b[j] = 9;
                    }
                }
                difvalue.push_back(lend * 10 + b[i] - a[i]);
                lend = 0;
            }
            else
            {
                difvalue.push_back(b[i] - a[i]);
            }
        }
        for (int i = strA.size(); i < strB.size(); i++)
        {
            difvalue.push_back(b[i]);
        }
    }
    //删 除 前 导 0
    for (int i = difvalue.size() - 1; i >= 0; i--)
    {
        if (difvalue[i] == 0)
        {
            difvalue.erase(difvalue.begin() + i);
        }
        else {
            break;
        }
    }
    //减法算法结束
    //下面为用迭代器输出
flag:
    cout << strA << "-" << strB << "=";
    //如果A比B小需要输出负号
    if (Comparevector(a, b) == 0)
    {
        cout << "-";
    }
    for (vector<int>::iterator it = difvalue.end() - 1; it >= difvalue.begin(); it--)
    {
        cout << *it;
        if (it == difvalue.begin())
        {
            break;
        }
    }
    cout << endl;
    //清内存
    vector<int>().swap(a);
    vector<int>().swap(b);
    vector<int>().swap(difvalue);
}
int Sub::Comparevector(vector<int>a, vector<int>b)//比较俩个vector容器内置的数的大小,传入的容器存的数是倒序的!
{
    //a比b打则返回1   a比b小则返回0   a与b等于则返回3
    //首先将数变成正序
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    if (a.size() > b.size())
        return 1;
    if (a.size() < b.size())
        return 0;
    if (a.size() == b.size())
    {
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] > b[i])
                return 1;
            if (a[i] < b[i])
                return 0;
        }
        return 3;
    }
}

class Mul : public Compute //这是乘法类
{
    virtual void compute(string& strA, string& strB) override;
    vector<int> Muladd(vector<int>& a, vector<int>& b); //定义 乘法内置加法函数
};
void Mul::compute(string& strA, string& strB)
{
    vector<int> a;       // a容器中存放第一个数
    vector<int> b;       // b容器中存放第二个数
    vector<int> product; // product容器中存放俩数的乘积
    vector<int> temp;    // temp容器为工具容器 用于储存 计算过程中的步骤
    int index = 0;       //定义进位为0 Index
                         //乘法也是从小位开始算起 所以也采用逆序储存逆序输出
    for (int i = strA.size() - 1; i >= 0; i--)
    {
        a.push_back(strA[i] - '0');
    }

    for (int i = strB.size() - 1; i >= 0; i--)
    {
        b.push_back(strB[i] - '0');
    }

    for (int i = 0; i < b.size(); i++)
    {
        for (int j = 0; j < a.size(); j++)
        {
            temp.push_back((a[j] * b[i] + index) % 10);
            index = (a[j] * b[i] + index) / 10;
        }
        for (int j = 0; j < i; j++)
        {
            temp.insert(temp.begin(), 0);
        }
        //执行加法  加法执行完毕后清空temp容器
        product = Muladd(temp, product);
        temp.clear();
    }

    if (index != 0)
    {
        product.push_back(index);
    }
    //乘法计算结束
    //接下来为 迭代器输出储存乘积的容器 product
    cout << strA << "*" << strB << "=";
    for (vector<int>::iterator it = product.end() - 1; it >= product.begin(); it--)
    {
        cout << *it;
        if (it == product.begin())
        {
            break;
        }
    }
    cout << endl;
    //输出完毕 接下来进行容器清内存
    vector<int>().swap(a);
    vector<int>().swap(b);
    vector<int>().swap(temp);
    vector<int>().swap(product);
}
//对乘法内置加法函数的类外定义
vector<int> Mul::Muladd(vector<int>& a, vector<int>& b)
{
    //这个函数是实现两个容器的大数数据相加 与加法类一致
    int index = 0;   //设置进位
    vector<int> sum; //设置存放俩数和的容器 最后需要返回这个容器
    for (int i = 0; i < a.size() && i < b.size(); i++)
    {
        sum.push_back((index + a[i] + b[i]) % 10);
        index = (a[i] + b[i] + index) / 10;
    }
    //相等的位数已经相加完毕
    //接下来相加 独立的位数

    if (a.size() > b.size())
    {
        for (int i = b.size(); i < a.size(); i++)
        {
            sum.push_back((a[i] + index) % 10);
            index = (a[i] + index) / 10;
        }
    }

    if (a.size() < b.size())
    {
        for (int i = a.size(); i < b.size(); i++)
        {
            sum.push_back((b[i] + index) % 10);
            index = (b[i] + index) / 10;
        }
    }

    if (index != 0)
    {
        sum.push_back(1);
    }
    //计算完毕 返回算出的和容器vector
    //注意 这时候的 vector 仍然是小数在左。大数在右
    return sum;
}

class Division :public Compute//除法类
{
    virtual void compute(string& strA, string& strB) override;
    vector <int> divsub(vector<int>a, vector<int>b);//声明除法内置减法运算   运行的是第一个数减去第二个数
    int Compatrvector(vector<int>& a, vector<int>& b);//声明比较容器储存的数的大小的函数
};
void Division::compute(string& strA, string& strB)
{
    vector<int>a;//a容器存放第一个数 
    vector<int>b;//b容器存放第二个数
    vector<int>div;//div容器存放商

    //读取环节
    //因为除法的运算是从高位往低位进行运算 那么我们选择正向输入以方便运算
    for (int i = 0; i < strA.size(); i++)
    {
        a.push_back(strA[i] - '0');
    }

    for (int i = 0; i < strB.size(); i++)
    {
        b.push_back(strB[i] - '0');
    }

    //开始除法算法
    //1.将被除数位数用0补齐使得其长度和除数的长度相等
    //为了保留ab容器 利用复制构造创建新容器
    vector<int> B(b);
    vector<int> temp(a);
    //首先可以直接判断 俩数大小关系 如果前小于后直接输出0,没必要进行以下算法
    if (Compatrvector(a, b) == 0)
    {
        cout << strA << "/" << strB <<"=" << 0;
        return; 
    }

    if (b.size() == a.size())
    {
    int j = 0;
    while (Compatrvector(temp, B)!=0)
    {
        temp = divsub(temp, B);
        j++;
    }
    cout << strA << "/" << strB << "=" << j << endl;
    return;
  }

    int i;
    for (int i = B.size(); i < a.size(); i++)
    {
        B.push_back(0);
    }
    //2.判断补齐后的被除数与除数的大小关系(过程中不断更新除数,即每次差求商的余数)
    //->如果被除数的数值大于除数的数值 那么对被补齐的被除数进行退位操作,即退掉末位0   (似乎可以使用肯尼汉算法)
    //->如果被除数的数值小于除数的数值 那么进行除数循环减被除数求商 直到除数小于被除数
    //对以上操作进行循环
    //退出循环的条件 :补足的0已经退完 并且此时的除数小于被除数
    while (B.size() > b.size())
    {
        //这个只限于长度不相等  如果长度相等直接做减法很快得出答案!
        if (Compatrvector(B, temp) == 1)
        {

            B.pop_back();
            if (Compatrvector(B, temp) == 1)
            {
                div.push_back(0);
            }
        }
        if (Compatrvector(B, temp) != 1)
        {
            for (i = 1; i != 1.1; i++)
            {
                temp = divsub(temp, B);
                if (Compatrvector(temp, B) == 0)
                {
                    div.push_back(i);
                    i = 1;
                    break;
                }
            }
        }
    }
    //除法算法结束 
    //接下来为迭代器输出
    cout << strA << "/" << strB << "=";
    for (vector<int>::iterator it = div.begin(); it < div.end(); it++)
    {
        cout << *it;
    }
    //清理内存
    vector<int>().swap(a);
    vector<int>().swap(b);
    vector<int>().swap(temp);
    vector<int>().swap(div);
}
vector<int>Division::divsub(vector<int>a, vector<int>b)//为了防止参数被改变 采用 值传递
{
    vector<int> difvalue;
    //既然在除法里面的减法合理,那么一定是大数减小数  这里默认a>b
    //因为传进来的容器是正序的 所以为了计算方便 我们需要做倒序处理  
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lend = 0;//初始化借位
    //既然已经默认了 a>b  那么a的位数一定大于等于b的位数
    for (int i = 0; i < b.size(); i++)
    {
        if (a[i] < b[i])
        {
            for (int j = i + 1; j < a.size(); j++)//a向高位非0数借位
            {
                if (a[j] != 0)
                {
                    a[j] -= 1;
                    lend = 1;
                    break;
                }
                else
                {
                    a[j] = 9;//向0借位为9
                }
            }
        }
        difvalue.push_back(lend * 10 + a[i] - b[i]);
        lend = 0;
    }
    //接下来为a多出的位数
    for (int i = b.size(); i < a.size(); i++)
    {
        difvalue.push_back(a[i]);
    }
    //然后要让差恢复正常顺序
    reverse(difvalue.begin(), difvalue.end());
    for (int i = 0; i != 1.1; i++)
    {
        //删除前导0
        if (difvalue[0] == 0&&difvalue.size()!=1)
        {
            difvalue.erase(difvalue.begin(), difvalue.begin() + 1);
        }
        else
        {
            break;
        }
    }
    return difvalue;
}
int Division::Compatrvector(vector<int>& a, vector<int>& b)//这是内置在除法类中的比较函数 用于比较俩个正向储存的容器数的大小
//若a>b  则返回1   小于则返回0      相等则返回3
{
    if (a.size() > b.size())
        return 1;
    if (a.size() < b.size())
        return 0;
    if (a.size() == b.size())
    {
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] > b[i])
                return 1;
            if (a[i] < b[i])
                return 0;
        }
        return 3;
    }
}

int main()
{
    //首先询问用户需要输入的两个大数
    string strA, strB;
    char idea;
    cout << "**************欢迎使用高精度计算器**************" << endl << endl;   
    cout<< "**************输入E X E退出计算器**************" << endl << endl;
    cout << "请输入你要计算的算式(符号数字之间由空格隔开)<示例:1空格+空格1>:" << endl;
flag:
    cin >> strA >> idea >> strB;
    if (strA == "E" && strB == "E" && idea == 'X')
    {
        goto tp;
    }
    //计算大类我使用了多态  下面对函数进行调用  基类指针指向派生类
    switch (idea)
    {
    case '+':
    {
        Compute* add = new Add;
        add->compute(strA, strB);
        if (add != NULL)
        {
            delete add;
            add = nullptr;
        }
        break;
    }
    case '-':
    {
        Compute* sub = new Sub;
        sub->compute(strA, strB);
        if (sub != NULL)
        {
            delete sub;
            sub = nullptr;
        }
        break;
    }
    case '*':
    {
        Compute* mul = new Mul;
        mul->compute(strA, strB);
        if (mul != NULL)
        {
            delete mul;
            mul = nullptr;
        }
        break;
    }
    case'/':
    {
        Compute* division = new Division;
        division->compute(strA, strB);
        if (division != NULL)
        {
            delete division;
            division = nullptr;
        }
        break;
    }

    }
    cout<<endl << "————————————————————————" << endl;
    goto flag;
tp:
    cout<< "*************--===感谢您的使用===--*************" << endl << endl;
    return 0;
}

上一篇:0101 lc.2022数组


下一篇:leetcode 将一元数组转化为二元数组