C/C++数据结构与算法,一元多项式问题

发布网友发布时间：2022-05-19 04:30

我来回答

共1个回答

热心网友时间：2024-03-04 10:33

楼主你好，这是我最近写的，把输入的式子当作纯字符串处理，已要求的是一元多项式，我的支持多元多项式，最多可支持5个变元，当然你亦可以修改代码使之更具扩展性，可能算法比较复杂，不懂得随时问我^~^

/*********************************************

*Copyright (c++) 2013 by xihua_university

*Filename:第二章_常用数据结构_多项式相乘_13.cpp

*Function:计算两个多项式相乘

*Auther:heyanbo

*Final:2013,8,16~18

*********************************************/

#include<iostream>

#include<sstream>

#include<string>

#include<iomanip>

using namespace std;

//////////////////////////////////////////////////////////

struct recoder_inf

{ char character;

int number;

};

bool check_number(string s);//检查小项是否只含数字

string link_string(string s_f, string s_s, recoder_inf *temp_recoder);//运算并连接小项

///////////////////////////////////////////////////////////

int main()

{

char c;

int first(0), i(0), j(0), count(0), count1(0), k(0);

recoder_inf *temp_recoder = NULL;

string s_first, s_second, *s_f = NULL, *s_s = NULL, *link = NULL;

system("color 1e");

cout<<setw(46)<<setfill(' ')<<"多项式相乘运算器\n";

cout<<"请输入第一个多项式:(如2x^2+3xy+12,其中\"x^2\"表示x的平方)\n";

cin>>s_first;

cout<<"请输入第二个多项式:\n";

cin>>s_second;

while (((c='-',s_first.find(c,first)!=string::npos) \

&& s_first.find(c,first)<s_first.find('+',first))\

||(c='+',s_first.find(c,first)!=string::npos))//记录多项式1项数

{

count++;

first = s_first.find(c,first)+1;

}

if (s_first[0]=='-')//处理第一个小项带负号

count--;

s_f = new string[count+1];

first = 0;

if (s_first[0]=='-')//擦除负号

{

s_first.erase(0,1);

while (((c='-',s_first.find(c,first)!=string::npos) \

&& s_first.find(c,first)<s_first.find('+',first))\

||(c='+',s_first.find(c,first)!=string::npos))//拆解多项式1至小项

{

if (s_first[first-1]=='-')

s_f[i] = s_first.substr(first-1,s_first.find(c,first)-first+1);//保留负号

else

s_f[i] = s_first.substr(first,s_first.find(c,first)-first);

first = s_first.find(c,first)+1;

i++;

}

if (s_first[first-1]=='-')

s_f[i] = s_first.substr(first-1,s_first.length()-first+1);//处理最后一个小项

else

s_f[i] = s_first.substr(first,s_first.length()-first);

s_f[0].insert(0,'-');//插人负号

}

else

{

while (((c='-',s_first.find(c,first)!=string::npos) \

&& s_first.find(c,first)<s_first.find('+',first))\

||(c='+',s_first.find(c,first)!=string::npos))//拆解多项式1至小项

{

if (s_first[first-1]=='-')

s_f[i] = s_first.substr(first-1,s_first.find(c,first)-first+1);//保留负号

else

s_f[i] = s_first.substr(first,s_first.find(c,first)-first);

first = s_first.find(c,first)+1;

i++;

}

if (s_first[first-1]=='-')

s_f[i] = s_first.substr(first-1,s_first.length()-first+1);//处理最后一个小项

else

s_f[i] = s_first.substr(first,s_first.length()-first);

}

//////////////////////////////////////////////////////////////////////

first = 0;

while (((c='-',s_second.find(c,first)!=string::npos) \

&& s_second.find(c,first)<s_second.find('+',first))\

||(c='+',s_second.find(c,first)!=string::npos))//记录多项式2项数

{

count1++;

first = s_second.find(c,first)+1;

}

if (s_second[0]=='-')//处理第一个小项带负号

count1--;

s_s = new string [count1+1];

first = 0;

i = 0;

if (s_second[0]=='-')

{

s_second.erase(0,1);

while (((c='-',s_second.find(c,first)!=string::npos) \

&& s_second.find(c,first)<s_second.find('+',first))\

||(c='+',s_second.find(c,first)!=string::npos))//拆解多项式2至小项

{

if (s_second[first-1]=='-')

s_s[i] = s_second.substr(first-1,s_second.find(c,first)-first+1);//保留负号

else

s_s[i] = s_second.substr(first,s_second.find(c,first)-first);

first = s_second.find(c,first)+1;

i++;

}

if (s_second[first-1]=='-')

s_s[i] = s_second.substr(first-1,s_second.length()-first+1);//处理最后一个小项

else

s_s[i] = s_second.substr(first,s_second.length()-first);

s_s[0].insert(0,'-');//插入负号

}

else

{

while (((c='-',s_second.find(c,first)!=string::npos) \

&& s_second.find(c,first)<s_second.find('+',first))\

||(c='+',s_second.find(c,first)!=string::npos))//拆解多项式2至小项

{

if (s_second[first-1]=='-')

s_s[i] = s_second.substr(first-1,s_second.find(c,first)-first+1);//保留负号

else

s_s[i] = s_second.substr(first,s_second.find(c,first)-first);

first = s_second.find(c,first)+1;

i++;

}

if (s_second[first-1]=='-')

s_s[i] = s_second.substr(first-1,s_second.length()-first+1);//处理最后一个小项

else

s_s[i] = s_second.substr(first,s_second.length()-first);

}

/////////////////////////////////////////////////////////////////////////

link = new string[(count+1)*(count1+1)];

temp_recoder = new recoder_inf[20];//支持单个大项拥有最多10个不同变量

for (i=0;i<count+1;i++)//连接字符串并处理输出符号问题

for (j=0;j<count1+1;j++)

{

link[k] = link_string(s_f[i], s_s[j],temp_recoder);

if (link[k][0]=='1' && (link[k][1]<'0'||link[k][1]>'9') &&\

!check_number(link[k]))//系数为1就不要系数

link[k].erase(0,1);

if (link[k][0]=='-' && link[k][1]=='1' && \

(link[k][2]<'0'||link[k][2]>'9') && !check_number(link[k]))//系数为-1则只保留负号

link[k].erase(1,1);

if (link[k][0]!='-')

link[k].insert(0,'+');

if (i==0 && j==0 && link[k][0]!='-')

link[k].erase(0,1);

k++;

}

cout<<"计算结果如下:\n";

cout<<'(';

for (i=0;i<count+1;i++)

{

if (i!=0 && s_f[i][0]!='-')

{

s_f[i].insert(0,'+');

cout<<s_f[i];

}

else

cout<<s_f[i];

}

cout<<")*(";

for (j=0;j<count1+1;j++)

{

if (j!=0 && s_s[j][0]!='-')

{

s_s[j].insert(0,'+');

cout<<s_s[j];

}

else

cout<<s_s[j];

}

cout<<")=";

for (i=0;i<(count+1)*(count1+1);i++)

cout<<link[i];

cout<<endl;

delete []temp_recoder;

delete []s_f;

delete []s_s;

delete []link;

return 0;

}

/***检查小项是否为纯数字以便直接运算***/

bool check_number(string s)

{

for (int i=0;i<s.length();i++)

{

if (s[i]=='-' || s[i]>='0' && s[i]<='9' || s[i]=='.')

;

else

return false;

}

return true;

}

/***系数相乘并连接小项***/

string link_string(string s_f, string s_s,recoder_inf *temp_recoder)

{

char c_temp;

float s_f_temp(1.0), s_s_temp(1.0);

int t(0), t1, count(0), count1(0), count2(0), i, i1, j, m, n, k, r, r1, r_temp, l, l1;

string s, s1, s_temp;

stringstream f;

/***当第一个与第二个多项式都不全为数字时执行以下操作***/

if (!check_number(s_f) && !check_number(s_s))//检查小项的系数

{

///////////////////////////处理小项系数

for (i=0;i<s_f.length(); ) //对第一个多项式的小项依次做处理

{

if (s_f[i]=='-' || s_f[i]>='0'&&s_f[i]<='9' || s_f[i]=='.')//系数截取位置

i++;

else

break;

}

if (i==1 && s_f[0]=='-')

s_f_temp = -1;

elseif (i>=1)

s_f_temp = atof(s_f.substr(0,i).c_str());

for (i1=0;i1<s_s.length(); ) //对第二个多项式的小项依次做处理

{

if (s_s[i1]=='-' || s_s[i1]>='0'&&s_s[i1]<='9' || s_s[i1]=='.')//系数截取位置

i1++;

else

break;

}

if (i1==1 &&s_s[0]=='-')

s_s_temp = -1;

else if (i1>=1)

s_s_temp = atof(s_s.substr(0,i1).c_str());

f.clear();

f<<s_f_temp*s_s_temp;//类型安全转换

f>>s;

s_temp = s_f.substr(i,s_f.length()-i)+s_s.substr(i1,s_s.length()-i1);

///////////////////////////////////

for (j=0;j<s_temp.length(); )//对连接好的去除了系数的字符串做处理

{

if (((t1=s_temp.substr(0,j).find(s_temp[j],0))>=0?false:true) \

&& s_temp[j]!='^' && (s_temp[j]<'0'||s_temp[j]>'9'))//检查变元是否重复

{

temp_recoder[t].character = s_temp[j];

l1 = j;

if (s_temp[j+1]=='^')

{

for (m=j+2;m<s_temp.length();m++)

{

if (s_temp[m]>='0' && s_temp[m]<='9')

count++;

else

break;

}

temp_recoder[t].number = atoi(s_temp.substr(j+2,count).c_str());

j += 2+count;//下一个变元的位置

//////////////////////////////////处理下一变元

for (n=j;n<s_temp.length(); )

{

if (s_temp[n]==s_temp[l1] && s_temp[n+1]!='^')

{

count1++;

n++;

temp_recoder[t].number += count1;

}

if (s_temp[n]==s_temp[l1] && s_temp[n+1]=='^')

{

for (k=n+2;k<s_temp.length();k++)//变元指数截取位数

{

if (s_temp[k]>='0' && s_temp[k]<='9')

count2++;

else

break;

}

temp_recoder[t].number += atoi(s_temp.substr(n+2,count2).c_str());//变元指数

n +=2+count2;

}

if (s_temp[n]!=s_temp[l1])

n++;

}

else

{

temp_recoder[t].number = 1;

j++;//下一个变元的位置

count1 = 0;

for (n=j;n<s_temp.length(); )

{

if (s_temp[n]==s_temp[l1] && s_temp[n+1]!='^')

{

count1++;

temp_recoder[t].number += count1;

n++;

}

if (s_temp[n]==s_temp[l1] && s_temp[n+1]=='^')

{

count2 = 0;

for (k=n+2;k<s_temp.length();k++)//变元指数截取位数

{

if (s_temp[k]>='0' && s_temp[k]<='9')

count2++;

else

break;

}

temp_recoder[t].number += atoi(s_temp.substr(n+2,count2).c_str());//变元指数

n +=2+count2;

}

if (s_temp[n]!=s_temp[l1])

n++;

}

t++;

}

else

{

j++;

}

for (r=0;r<t-1;r++)//选择排序法确保最高指数变元在前面

{

r_temp = r;

for (r1=r+1;r1<t;r1++)

if (temp_recoder[r1].number<temp_recoder[r_temp].number)

r_temp = r1;

if (r_temp!=r)

{

l = temp_recoder[r].number;//指数交换

temp_recoder[r].number = temp_recoder[r_temp].number;

temp_recoder[r_temp].number = l;

c_temp = temp_recoder[r].character;//变元交换

temp_recoder[r].character = temp_recoder[r_temp].character;

temp_recoder[r_temp].character = c_temp;

}

for (r=t-1;r>-1;r--)

{

if (temp_recoder[r].number>1)

{

f.clear();//清空缓冲区

f<<temp_recoder[r].character<<'^'<<temp_recoder[r].number;

f>>s1;

s += s1;

}

if (temp_recoder[r].number==1)

{

f.clear();

f<<temp_recoder[r].character;

f>>s1;

s += s1;

}

return s;

}

/***当第一个不全为数字而第二个多项式全为数字时执行以下操作***/

if (!check_number(s_f) && check_number(s_s))

{

for (i=0;i<s_f.length(); ) //对第一个多项式的小项依次做处理

{

if (s_f[i]=='-' || s_f[i]>='0'&&s_f[i]<='9' || s_f[i]=='.')//系数截取位置

i++;

else

break;

}

if (i==1 && s_f[0]=='-')

s_f_temp = -1;

else if (i>=1)

s_f_temp = atof(s_f.substr(0,i).c_str());

s_s_temp = atof(s_s.c_str());

f.clear();

f<<s_f_temp*s_s_temp<<s_f.substr(i,s_f.length()-i);

f>>s;

return s;

}

/***当第一个全为数字而第二个多项式不全为数字时执行以下操作***/

if (check_number(s_f) && !check_number(s_s))

{

for (i=0;i<s_s.length(); ) //对第一个多项式的小项依次做处理

{

if (s_s[i]=='-' || s_s[i]>='0'&&s_s[i]<='9' || s_s[i]=='.')//系数截取位置

i++;

else

break;

}

if (i==1 && s_s[0]=='-')

s_s_temp = -1;

else if (i>=1)

s_s_temp = atof(s_s.substr(0,i).c_str());

s_f_temp = atof(s_f.c_str());

f.clear();

f<<s_f_temp*s_s_temp<<s_s.substr(i,s_s.length()-i);

f>>s;

return s;

}

/***当第一个和第二个多项式全为数字时执行以下操作***/

if (check_number(s_f) && check_number(s_s))

{

s_f_temp = atof(s_f.c_str());

s_s_temp = atof(s_s.c_str());

f.clear();

f<<s_f_temp*s_s_temp;

f>>s;

return s;

}

追问=_=和我们的作业要求不一样。。所以没法采纳。。。