论坛 › 数据结构与算法 › 任意长度的大数加法（栈的应用）

caopeirui 发表于 2016-7-21 16:15:08

123333333333333

18577318294 发表于 2016-9-4 22:17:17

我来

一个厉害的名字 发表于 2016-9-8 10:49:14

{:10_254:}

lb2616 发表于 2016-9-10 14:00:44

学习

陶逗逗 发表于 2016-10-30 14:48:27

感觉很6

zzzz76 发表于 2016-10-31 22:24:02

写了三个while，感觉复杂度有些高，不知对不对

84561475 发表于 2017-3-16 09:57:55

我写的感觉好复杂用了三个stack

#include<iostream>

using namespace std;


const int STOCK_SIZE = 100;//定义栈的大小

template<class DataType>
class DSStack
{
public:
        DSStack(DataType[], int);
        DSStack();
        ~DSStack();
        void Push(DataType data);
        DataType Pop();
        void Clear();
        void Print();
        DataType GetTopData();
private:
        DataType elem;
        DataType *top;
        DataType *bottom;
        int Count;
};

template<class DataType>
DSStack<DataType>::DSStack(DataType data[], int len)
{
        bottom = elem;// 栈底初始指向
        top = bottom;   // 初始栈底与栈顶指针指向相同的位置
        for (int i = 1; i <= len; i++)
        {
                elem = data;
                Count++;
        }
}

template<class DataType>
DSStack<DataType>::DSStack()
{
        bottom = elem;// 栈底初始指向
        top = bottom;   // 初始栈底与栈顶指针指向相同的位置
        Count = 0;
}

template<class DataType>
DSStack<DataType>::~DSStack()
{
}

template<class DataType>
void DSStack<DataType>::Push(DataType data)
{
        if (Count > STOCK_SIZE) return;
        Count++;
        elem = data;
}

template<class DataType>
DataType DSStack<DataType>::Pop()
{
        if (Count < 1)return -1;
        DataType data;
        data = elem;
        Count--;
        return data;
}

template<class DataType>
void DSStack<DataType>::Clear()
{
        top = bottom;
        Count = 0;
}

template<class DataType>
void DSStack<DataType>::Print()
{
        cout << "栈的数据: " << endl;
        for (int i = 1; i <= Count; i++)
        {
                cout << " " << elem << endl;
        }
}

template<class DataType>
DataType DSStack<DataType>::GetTopData()
{
        if (Count == 0) return -1;
        return elem;
}

void main()
{
        DSStack<char> *stack_addend = new DSStack<char>();
        DSStack<char> *stack_augend = new DSStack<char>();
        DSStack<int> *stack_retult = new DSStack<int>();

        cout << "请输入加数以#结束" << endl;
        char s = ' ';
        cin >> s;
        while (s != '#')
        {
                stack_addend->Push(s);
                cin >> s;
        }
        stack_addend->Print();

        cout << "请输入被加数以#结束" << endl;
        s = ' ';
        cin >> s;
        while (s != '#')
        {
                stack_augend->Push(s);
                cin >> s;
        }
        stack_augend->Print();
        bool is_carry = false;// 是否进位
        while ((stack_addend->GetTopData() != -1) || (stack_augend->GetTopData() != -1) || is_carry)
        {
               
                // 考虑到两个数的位数不一定相等，把没有的弄为0
                if (stack_addend->GetTopData() == -1)
                {
                        stack_addend->Pop();
                        stack_addend->Push(48);
                }
                if (stack_augend->GetTopData() == -1)
                {
                        stack_augend->Pop();
                        stack_augend->Push(48);
                }

                char addend = stack_addend->Pop();
                char augend = stack_augend->Pop();

                int result = 0;
                if (is_carry)
                {
                        result = ((int)addend - 48) + ((int)augend - 48) + 1;
                        is_carry = false;
                }
                else
                {
                        result = ((int)addend - 48) + ((int)augend - 48);
                }
               
                if (result >= 10) // 如果的出来的结果是两位数
                {
                        int temp = result % 10;
                        stack_retult->Push(temp);
                        is_carry = true;
                        //stack_retult->Push(result / 10);
                }
                else
                {
                        stack_retult->Push(result);
                }
               
        }

        stack_retult->Print();
        getchar();
        getchar();
}

wangjia911 发表于 2017-6-1 02:31:53

学习

莱昂纳多 发表于 2017-7-20 21:57:14

啊师傅

yeahbijin 发表于 2017-8-25 15:21:26

嗜睡的小哥 发表于 2017-8-25 21:27:53

{:10_256:}看看

生炒牛肉饭42 发表于 2017-9-18 08:03:19

谢谢小甲鱼老师啊啊啊啊啊啊

xiaocangshu886 发表于 2017-9-26 09:58:21

1

Elevenx 发表于 2017-9-26 16:44:38

对答案

aiblue 发表于 2017-10-15 22:32:59

学习学习。

ljxll326 发表于 2017-12-23 12:00:05

a

崔文浩 发表于 2017-12-30 11:15:20

就能

圣狄雅哥 发表于 2018-2-3 09:29:18

{:5_91:}

圣狄雅哥 发表于 2018-2-3 10:57:28

carry是char型的，但赋值时carry = 0，可以将整形数据赋值给字符型吗

圣狄雅哥 发表于 2018-2-3 10:58:25

谁参照它编一个减法器、乘法器

查看完整版本: 任意长度的大数加法（栈的应用）