BDZNH
0%

一个超乎预料的程序

Posted on Edited on
Symbols count in article: Reading time ≈ NaN:aN

写着写着，发现有点超乎想象，没想到写那么长时间

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
/*
没想到会用那么长时间，果然是说得容易，做得难。
思路是分别提取每个单项式的系数(系数可以确定改单项式的符号)、指数
标准的单项式由以下部分组成
[符号-/+][系数][x^][指数]

当指数为0时  显示为(看起来是)
n

当系数为±1且指数为1时   显示为
x

当系数不为±1且指数为1时  显示为
nx

其他的为标准形式的单项式
±nx^a

*/
#include <stdio.h>
#include <stdlib.h>

//分别定义解决程序所需的七个功能的函数
void Addition();
void Soustraction();
void Multiplication();
void Division();
void Euclid();
void Factorization();

//这个结构体，用来存储提取后的系数、指数和符号
struct Array_poly
{
    int coefficient;//系数
    int index;//指数
    char symbol;//符号
};

//show_info用来显示屏幕的提示信息
void show_info()
{
    printf(" + : Addition\n - : Soustraction\n * : Multiplication\n / : Division\n d : Derivation\n e : Euclid\n f : Factorization\n q : Quit\ncmd> ");
}

int main()
{
    //freopen("data.txt","r",stdin);
    char str;
    show_info();
    while(scanf("%c",&str)!=EOF)//读入用户所选 '+'/-/*......
    {
        switch(str)
        {
            case '+' : Addition(); break;
            //case '-' : Soustraction(); break;
            //case '*' : Multiplication(); break;
            //case '/' : Division(); break;
            //case 'd' : Derivation(); break;
            //case 'e' : Euclid(); break;
            //case 'f' : Euclid; break;
            case 'q' : return 0; break;
            default : continue;
        }
        show_info();
    }
    printf("\nBoom\n");
    return 0;
}

//执行将两个多项式加起来的选项。
void Addition()
{
    char p1x[100]={0},p2x[100]={0};//用于存储p1(x)和p2(x)两个字符串
    int i=0,j=0,tmp=0,flag=0,k=0;
    //int coefficient;
    struct Array_poly ans[20]={{0,0,0}},ans2[20]={{0,0,0}};//用于存储提取出来的系数、指数、符号;
    printf("p1(x) = ");//提示信息
    scanf("%s",p1x);
    printf("p2(x) = ");//提示信息
    scanf("%s",p2x);


    while(p1x[i])//用于提取p1(x)字符串的指数、系数、符号
    {
        if(i==0&&p1x[i]=='-')//若第一个字符为'-'，则将ans(结构体)的第0个位置的符号记为'-'
            ans[i++].symbol='-';
        if(i==0&&(p1x[i]>='0'&&p1x[i]<='9'))//若第一个字符是一个数组，则将ans(结构体)的第0个位置的符号记为'+'，实际上，这里也留了一个bug，如果第一个字符为'+'(不标准输入)
            ans[i].symbol='+';
        if(p1x[i]=='x'&&p1x[i+1]!='^')//用于处理指数为1的情况
        {
            if(tmp==0)
                tmp=1;
            //ans[j].symbol=p1x[i-1];
            if(ans[j].symbol=='-')
            {
                ans[j].coefficient=0-tmp;
                ans[j++].index=1;
            }
            else
            {
                ans[j].coefficient=tmp;
                ans[j++].index=1;
            }
            i++;
            tmp=0;
            continue;
        }
        if(p1x[i]=='x')//指数不为1的情况
        {
            if(tmp==0)
                tmp=1;
            ans[j].coefficient=tmp;
            tmp=0;
            if(ans[j].symbol=='-')
                ans[j].coefficient=0-ans[j].coefficient;
            i++;
            flag=1;//标记，这个比较重要，标记这个单项式是标准单项式
            continue;
        }
        if(p1x[i]>='0'&&p1x[i]<='9')//用于提取系数或者指数，并存储在临时的变量tmp中
        {
            tmp=tmp*10+p1x[i]-48;
        }
        if(flag==0&&(p1x[i+1]==0||p1x[i+1]=='+'||p1x[i+1]=='-')&&p1x[i]>='0'&&p1x[i]<='9')//当单项式不标准，也就是，单项式为一个纯数字的情况
        {
            ans[j].coefficient=tmp;
            ans[j].index=0;
            if(ans[j].symbol=='-')
                ans[j].coefficient=0-ans[j].coefficient;
            //ans[++j].symbol=p1x[i];
            i++;
            tmp=0;
            continue;
        }
        if(p1x[i]=='+'||p1x[i]=='-')//遇到一个±号的时候，这个时候这个单项式已经读取 完毕
        {
            if(p1x[i-1]=='x')//如果这个±前面是一个'x'，那么改单项式为指数为1的单项式。
            {
                ans[j].symbol=p1x[i];
                i++;
                continue;
            }
            else //如果是标准单项式，则存储该单项式的符号和指数
            {
                ans[j].index=tmp;
                ans[++j].symbol=p1x[i];//这个++j好好斟酌一下
            }
            flag=0;//将flag清零，表示这个单项式已经存储完毕
            tmp=0;//用于存储系数或者指数的tmp清零
        }
        i++;
    }

    j++;
    i=flag=tmp=0;//同样是清零，防止影响p2(x)的提取
    while(p2x[i])
    {
        if(i==0&&p2x[i]=='-')
        {
            ans[j].symbol='-';
            i++;
        }
        if(i==0&&(p2x[i]>='0'&&p2x[i]<='9'))
        {
            ans[j].symbol='+';
        }

        if(p2x[i]=='x'&&p2x[i+1]!='^')
        {
            if(tmp==0)
                tmp=1;
            //ans[j].symbol=p1x[i-1];
            if(ans[j].symbol=='-')
            {
                ans[j].coefficient=0-tmp;
                ans[j++].index=1;
            }
            else
            {
                ans[j].coefficient=tmp;
                ans[j++].index=1;
            }
            i++;
            tmp=0;
            continue;
        }
        if(p2x[i]=='x')
        {
            if(tmp==0)
                tmp=1;
            ans[j].coefficient=tmp;
            tmp=0;
            if(ans[j].symbol=='-')
                ans[j].coefficient=0-ans[j].coefficient;
            i++;
            flag=1;
            continue;
        }
        if(p2x[i]>='0'&&p2x[i]<='9')
        {
            tmp=tmp*10+p2x[i]-48;
        }
        if(flag==0&&(p2x[i+1]==0||p2x[i+1]=='+'||p2x[i+1]=='-')&&(p2x[i]>='0'&&p2x[i]<='9'))
        {
            ans[j].coefficient=tmp;
            ans[j].index=0;
            if(ans[j].symbol=='-')
                ans[j].coefficient=0-ans[j].coefficient;
            //ans[++j].symbol=p2x[i];
            i++;
            tmp=0;
            continue;
        }
        if(p2x[i]=='+'||p2x[i]=='-')
        {
            if(p2x[i-1]=='x')
            {
                ans[j].symbol=p2x[i];
                i++;
                continue;
            }
            else
            {
                ans[j].index=tmp;
                ans[++j].symbol=p2x[i];
            }
            flag=0;
            tmp=0;
        }
        i++;
    }

    //j++;
    flag=1;
    while(flag) //此时已经将p1(x)和p2(x)的系数、指数、符号都存储于ans中了，现在将他们按照指数的大小，从小到大排序，算法为冒泡。
    {
        flag=0;
        for(i=1;i<=j;i++)
        {
            if(ans[i].index<ans[i-1].index)
            {
                flag=ans[i].index;//嗯，这里把flag当作一个过渡变量来用了(其实我只是懒得多定义一个过渡变量)
                ans[i].index=ans[i-1].index;
                ans[i-1].index=flag;
                flag=ans[i].coefficient;
                ans[i].coefficient=ans[i-1].coefficient;
                ans[i-1].coefficient=flag;
                flag=ans[i].symbol;
                ans[i].symbol=ans[i-1].symbol;
                ans[i-1].symbol=flag;
                flag=1;

            }
        }
    }


    //将同类项合并，并存储到ans2中
    ans2[0].coefficient=ans[0].coefficient;
    ans2[0].index=ans[0].index;
    ans2[0].symbol=ans[0].symbol;
    for(i=1;i<=j;i++)
    {
        if(ans[i].index==ans2[k].index)
        {
            ans2[k].coefficient+=ans[i].coefficient;
        }
        else
        {
            ans2[++k].coefficient=ans[i].coefficient;
            ans2[k].index=ans[i].index;
            ans2[k].symbol=ans[i].symbol;
        }
    }



    printf("p1(x) + p2(x) = ");//准备输出啦
    for(i=0;i<=k;i++)
    {
        if(ans2[i].coefficient==0)//若系数为零，则直接进行下一个循环
            continue;
        if(ans2[i].coefficient==1)//系数为1的情况
        {
            if(tmp)//系数是正数，且不是第一次输出的话，需要输出一个'+'号，因为正数输出，不带符号
            {
                if(ans2[i].index!=0)//若系数为1且指数不为0，则输出x^ans[i].index
                    printf("+x^%d",ans2[i].index);
                else
                    printf("+1");//若系数为1且指数为0，则输出1
            }
            else//系数是正数，且是第一次输出的话，标记一下tmp，表示已经输出过了，第一次输出如果为正数，是不需要输出'+'的
            {
                if(ans2[i].index!=0)
                    printf("x^%d",ans2[i].index);
                else
                    printf("1");
                tmp=1;
            }
            continue;
        }
        if(ans2[i].coefficient>0)//系数不为0、不为1，且大于0的时候
        {
            if(tmp)//系数是正数，且不是第一次输出的话，需要输出一个'+'号，因为正数输出，不带符号'+'
            {
                if(ans2[i].index!=0)
                    printf("+%dx^%d",ans2[i].coefficient,ans2[i].index);
                else
                    printf("+%d",ans2[i].coefficient);
            }

            else//系数是正数，且是第一次输出的话，标记一下tmp，表示已经输出过了，第一次输出如果为正数，是不需要输出'+'的
            {
                if(ans2[i].index!=0)
                    printf("%dx^%d",ans2[i].coefficient,ans2[i].index);
                else
                    printf("%d",ans2[i].coefficient);
                tmp=1;
            }
        }
        else//系数小于0的情况，直接输出就好了，因为负数自己带着'-'号
        {
            printf("%dx^%d",ans2[i].coefficient,ans2[i].index);
            tmp=1;
        }
    }
    printf("\n");
}

运行示例

解析

从字符串中提取系数、指数、符号

思路是这样的：
对于正常的单项式[±][n]x^[a](a为整数，n为正整数),遇到字符“x”的时候，表示它前面的数字是系数，遇到字符“±”时，表示它前面的数字是指数。
系数或者指数用这样的办法来提取

1
2
3
4
5
6
i=tmp=0;
while(str[i]>='0'&&str[i]<='9')
{
    tmp=tmp*10+str[i]-48;//减去48的原因是我们将多项式当作字符串读入，要将字符'0'或者'1'之类的转化成相对应的整数，得减去48之后赋值给一个int类型的变量。
    i++;
}

这样，我们就拿到系数或者指数了
当遇到一个x的时候，需要将拿到的系数tmp给保存起来，那就这样做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(str[i]=='x')
{
    {
            if(tmp==0)//若tmp为0，表示x前面是一个“±”号，也就是系数为1的情况，那么tmp是不会变成1的，所以这里判断之后，将tmp变成1
                tmp=1;
            ans[j].coefficient=tmp;//将tmp存储
            tmp=0;
            if(ans[j].symbol=='-')//若这个单项式的符号为“-”，那么就将存储好的系数变成负数
                ans[j].coefficient=0-ans[j].coefficient;
            i++;
            flag=1;//标记，这个比较重要，标记这个单项式是有指数的单项式，也就是说，标记一下这个单项式不是纯数字
            continue;
        }
}

当遇到一个“±”号的时候，需要将拿到的指数tmp保存，这样做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if(p1x[i]=='+'||p1x[i]=='-')//遇到一个±号的时候，这个时候这个单项式已经读取 完毕
{
    if(p1x[i-1]=='x')//如果这个±前面是一个'x'，那么该单项式为指数为1的单项式。
    {
        ans[j].symbol=p1x[i];
        i++;
        continue;
    }
    else //如果是标准单项式，则存储该单项式的符号和指数
    {
        ans[j].index=tmp;
        ans[++j].symbol=p1x[i];//将j加一个1，准备存储下一个系数、指数、符号
    }
    flag=0;//将flag清零，表示这个单项式已经存储完毕
    tmp=0;//用于存储系数或者指数的tmp清零
}

对于指数为1的情况，特殊对待一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if(p1x[i]=='x'&&p1x[i+1]!='^')//用于处理指数为1的情况，也就是，遇到一个“x”，但是它后面不是“^”的情况
{
    if(tmp==0)
        tmp=1;
    //ans[j].symbol=p1x[i-1];
    if(ans[j].symbol=='-')
    {
        ans[j].coefficient=0-tmp;
        ans[j++].index=1;
    }
    else
    {
        ans[j].coefficient=tmp;
        ans[j++].index=1;
    }
    i++;
    tmp=0;
    continue;
}

对于单项式为纯数字的情况

1
2
3
4
5
6
7
8
9
10
11
12
if(flag==0&&(p1x[i+1]==0||p1x[i+1]=='+'||p1x[i+1]=='-')&&p1x[i]>='0'&&p1x[i]<='9')//当单项式不标准，也就是，单项式为一个纯数字的情况
//若flag为0，且当前字符是一个数字，且这个字符后面是“±”号或者字符串末尾，则这个单项式是纯数字
{
    ans[j].coefficient=tmp;
    ans[j].index=0;
    if(ans[j].symbol=='-')
        ans[j].coefficient=0-ans[j].coefficient;
    //ans[++j].symbol=p1x[i];
    i++;
    tmp=0;
    continue;
}

合并同类项

经过一番奋战，我们终于拿到了两个字符串的系数、指数、符号了，并且把他们都存储在了ans中，合并同类项之前，先把他们按照系数，从小到大排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
flag=1;
while(flag) //此时已经将p1(x)和p2(x)的系数、指数、符号都存储于ans中了，现在将他们按照指数的大小，从小到大排序，算法为冒泡。
{
    flag=0;
    for(i=1;i<=j;i++)
    {
        if(ans[i].index<ans[i-1].index)
        {
            flag=ans[i].index;//嗯，这里把flag当作一个过渡变量来用了(其实我只是懒得多定义一个过渡变量)
            ans[i].index=ans[i-1].index;
            ans[i-1].index=flag;
            flag=ans[i].coefficient;
            ans[i].coefficient=ans[i-1].coefficient;
            ans[i-1].coefficient=flag;
            flag=ans[i].symbol;
            ans[i].symbol=ans[i-1].symbol;
            ans[i-1].symbol=flag;
            flag=1;

        }
    }
}

然后合并同类项(我将合并后的多项式存储到ans2中)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ans2[0].coefficient=ans[0].coefficient;
ans2[0].index=ans[0].index;
ans2[0].symbol=ans[0].symbol;
for(i=1;i<=j;i++)
{
    if(ans[i].index==ans2[k].index)
    {
        ans2[k].coefficient+=ans[i].coefficient;
    }
    else
    {
        ans2[++k].coefficient=ans[i].coefficient;
        ans2[k].index=ans[i].index;
        ans2[k].symbol=ans[i].symbol;
    }
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
printf("p1(x) + p2(x) = ");//准备输出啦
for(i=0;i<=k;i++)
{
    if(ans2[i].coefficient==0)//若系数为零，则直接进行下一个循环
        continue;
    if(ans2[i].coefficient==1)//系数为1的情况
    {
        if(tmp)//系数是正数，且不是第一次输出的话，需要输出一个'+'号，因为正数输出，不带符号
        {
            if(ans2[i].index!=0)//若系数为1且指数不为0，则输出x^ans2[i].index
                printf("+x^%d",ans2[i].index);
            else
                printf("+1");//若系数为1且指数为0，则输出1
        }
        else//系数是正数，且是第一次输出的话，标记一下tmp，表示已经输出过了，第一次输出如果为正数，是不需要输出'+'的
        {
            if(ans2[i].index!=0)
                printf("x^%d",ans2[i].index);
            else
                printf("1");
            tmp=1;
        }
        continue;
    }
    if(ans2[i].coefficient>0)//系数不为0、不为1，且大于0的时候
    {
        if(tmp)//系数是正数，且不是第一次输出的话，需要输出一个'+'号，因为正数输出，不带符号'+'
        {
            if(ans2[i].index!=0)
                printf("+%dx^%d",ans2[i].coefficient,ans2[i].index);
            else
                printf("+%d",ans2[i].coefficient);
        }

        else//系数是正数，且是第一次输出的话，标记一下tmp，表示已经输出过了，第一次输出如果为正数，是不需要输出'+'的
        {
            if(ans2[i].index!=0)
                printf("%dx^%d",ans2[i].coefficient,ans2[i].index);
            else
                printf("%d",ans2[i].coefficient);
            tmp=1;
        }
    }
    else//系数小于0的情况，直接输出就好了，因为负数自己带着'-'号
    {
        printf("%dx^%d",ans2[i].coefficient,ans2[i].index);
        tmp=1;
    }
}

生命重在折腾