任意长度的大数加法（栈的应用）

18577318294

我来

一个厉害的名字

lb2616

学习

陶逗逗

感觉很6

zzzz76

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

84561475

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

1. #include<iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. 
   
6. const int STOCK_SIZE = 100;//定义栈的大小  
   
7. 
   
8. template<class DataType>
   
9. class DSStack
   
10. {
    
11. public:
    
12.         DSStack(DataType[], int);
    
13.         DSStack();
    
14.         ~DSStack();
    
15.         void Push(DataType data);
    
16.         DataType Pop();
    
17.         void Clear();
    
18.         void Print();
    
19.         DataType GetTopData();
    
20. private:
    
21.         DataType elem[STOCK_SIZE];
    
22.         DataType *top;
    
23.         DataType *bottom;
    
24.         int Count;
    
25. };
    
26. 
    
27. template<class DataType>
    
28. DSStack<DataType>::DSStack(DataType data[], int len)
    
29. {
    
30.         bottom = elem;  // 栈底初始指向
    
31.         top = bottom;   // 初始栈底与栈顶指针指向相同的位置
    
32.         for (int i = 1; i <= len; i++)
    
33.         {
    
34.                 elem[i] = data[i];
    
35.                 Count++;
    
36.         }
    
37. }
    
38. 
    
39. template<class DataType>
    
40. DSStack<DataType>::DSStack()
    
41. {
    
42.         bottom = elem;  // 栈底初始指向
    
43.         top = bottom;   // 初始栈底与栈顶指针指向相同的位置
    
44.         Count = 0;
    
45. }
    
46. 
    
47. template<class DataType>
    
48. DSStack<DataType>::~DSStack()
    
49. {
    
50. }
    
51. 
    
52. template<class DataType>
    
53. void DSStack<DataType>::Push(DataType data)
    
54. {
    
55.         if (Count > STOCK_SIZE) return;
    
56.         Count++;
    
57.         elem[Count] = data;
    
58. }
    
59. 
    
60. template<class DataType>
    
61. DataType DSStack<DataType>::Pop()
    
62. {
    
63.         if (Count < 1)  return -1;
    
64.         DataType data;
    
65.         data = elem[Count];
    
66.         Count--;
    
67.         return data;
    
68. }
    
69. 
    
70. template<class DataType>
    
71. void DSStack<DataType>::Clear()
    
72. {
    
73.         top = bottom;
    
74.         Count = 0;
    
75. }
    
76. 
    
77. template<class DataType>
    
78. void DSStack<DataType>::Print()
    
79. {
    
80.         cout << "栈的数据: " << endl;
    
81.         for (int i = 1; i <= Count; i++)
    
82.         {
    
83.                 cout << " " << elem[i] << endl;
    
84.         }
    
85. }
    
86. 
    
87. template<class DataType>
    
88. DataType DSStack<DataType>::GetTopData()
    
89. {
    
90.         if (Count == 0) return -1;
    
91.         return elem[Count];
    
92. }
    
93. 
    
94. void main()
    
95. {
    
96.         DSStack<char> *stack_addend = new DSStack<char>();
    
97.         DSStack<char> *stack_augend = new DSStack<char>();
    
98.         DSStack<int> *stack_retult = new DSStack<int>();
    
99. 
    
100.         cout << "请输入加数以#结束" << endl;
     
101.         char s = ' ';
     
102.         cin >> s;
     
103.         while (s != '#')
     
104.         {
     
105.                 stack_addend->Push(s);
     
106.                 cin >> s;
     
107.         }
     
108.         stack_addend->Print();
     
109. 
     
110.         cout << "请输入被加数以#结束" << endl;
     
111.         s = ' ';
     
112.         cin >> s;
     
113.         while (s != '#')
     
114.         {
     
115.                 stack_augend->Push(s);
     
116.                 cin >> s;
     
117.         }
     
118.         stack_augend->Print();
     
119.         bool is_carry = false;  // 是否进位
     
120.         while ((stack_addend->GetTopData() != -1) || (stack_augend->GetTopData() != -1) || is_carry)
     
121.         {
     
122.                
     
123.                 // 考虑到两个数的位数不一定相等，把没有的弄为0
     
124.                 if (stack_addend->GetTopData() == -1)
     
125.                 {
     
126.                         stack_addend->Pop();
     
127.                         stack_addend->Push(48);  
     
128.                 }
     
129.                 if (stack_augend->GetTopData() == -1)
     
130.                 {
     
131.                         stack_augend->Pop();
     
132.                         stack_augend->Push(48);
     
133.                 }
     
134. 
     
135.                 char addend = stack_addend->Pop();
     
136.                 char augend = stack_augend->Pop();
     
137. 
     
138.                 int result = 0;
     
139.                 if (is_carry)
     
140.                 {
     
141.                         result = ((int)addend - 48) + ((int)augend - 48) + 1;
     
142.                         is_carry = false;
     
143.                 }
     
144.                 else
     
145.                 {
     
146.                         result = ((int)addend - 48) + ((int)augend - 48);
     
147.                 }
     
148.                
     
149.                 if (result >= 10) // 如果的出来的结果是两位数
     
150.                 {
     
151.                         int temp = result % 10;
     
152.                         stack_retult->Push(temp);
     
153.                         is_carry = true;
     
154.                         //stack_retult->Push(result / 10);
     
155.                 }
     
156.                 else
     
157.                 {
     
158.                         stack_retult->Push(result);
     
159.                 }
     
160.                
     
161.         }
     
162. 
     
163.         stack_retult->Print();
     
164.         getchar();
     
165.         getchar();
     
166. }

复制代码

wangjia911

学习

莱昂纳多

啊师傅

嗜睡的小哥

看看

生炒牛肉饭42

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

xiaocangshu886

1

Elevenx

对答案

aiblue

学习学习。

ljxll326

a

崔文浩

就能

圣狄雅哥

圣狄雅哥

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

圣狄雅哥

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

圣狄雅哥

//实现输入任意长度字符串的整数减法
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqstack;

void Initstack(sqstack *s)
{
    s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if(!s->base)
    {
        exit(0);
    }
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}

void push(sqstack*s,ElemType e)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(ElemType*)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(ElemType));
        if(!s->base)
        {
            exit(0);
        }
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    *(s->top++)=e;
}

void pop(sqstack*s,ElemType*e)
{
    if(s->top==s->base)
    {
        return;
    }
    *e=*(--s->top);
}

int stacklen(sqstack *s)
{
    return (s->top-s->base);
}

void SUBTRACTION(sqstack*s1,sqstack*s2,sqstack*s3)
{
    char a,b,c;
    char carry=0;
    while(stacklen(s1)!=0&&stacklen(s2)!=0)
    {
        pop(s1,&a);
        pop(s2,&b);
        c=(a-48)-(b-48)-carry+48;
        if(c<'0')
        {
            c=c+'9'-47;
            carry=1;
        }
        else
        {
            carry=0;
        }
        push(s3,c);
    }
    if(stacklen(s1)!=0)
    {
        while(stacklen(s1)!=0)
        {
            pop(s1,&a);
            c=a-carry;
            if(c<'0')
           {
              c=c+'9'-47;
              carry=1;
           }
           else
          {
             carry=0;
          }
        push(s3,c);
        }
    }
    else if(stacklen(s2)!=0)
    {
        while(stacklen(s2)!=0)
        {
            pop(s2,&b);
            c='0'-carry-b;
            carry=1;
            c=c+'9'-47;
        push(s3,c);
        }
    }
    if(carry==1)
    {
        while(stacklen(s3)!=0)
        {
            pop(s3,&b);
            push(s2,b);
        }
        carry=0;
        while(stacklen(s2)!=0)
        {
            pop(s2,&b);
            c='9'-b+49-carry;
            push(s3,c);
            carry=1;
        }
        push(s3,'-');
    }
}

int main()
{
    char e;
    sqstack s1, s2, s3;

    Initstack(&s1);
    Initstack(&s2);
    Initstack(&s3);

    printf("请输入第一串任意整数，输入＃表示结束：");
    scanf("%c", &e);
    while( e != '#' )
    {
        push(&s1, e);
        scanf("%c", &e);
    }
    getchar();      // 回收回车符

    printf("\n请输入第二串任意整数，输入＃表示结束：");
    scanf("%c", &e);
    while( e != '#' )
    {
        push(&s2, e);
        scanf("%c", &e);
    }
    getchar();      // 回收回车符

    SUBTRACTION(&s1, &s2, &s3);

    printf("\n两者的差是：");
    while(stacklen(&s3) != 0)
    {
        pop(&s3, &e);
        printf("%c", e);
    }

    return 0;
}