更新时间:2022-08-12 18:39:54
题目
背景:
编程实现如下功能:对输入的一元多项式,进行同类项合并,并按指数降序排序,输出处理后的一元多项式。
说明:
格式说明
一元多项式输入输出时以字符串形式表示,格式如下
注意:输入多项式符合上述格式,无需检查;输出多项式格式由考生程序保证
规格
输入多项式满足如下规格,考生程序无需检查:
–0<单项式系数<=1000<>
–0<=单项式指数<=3000<>
–单项式个数不限制,但同类项合并处理后,单项式的系数小于65535。
示例
例一
输入:
"7X^4-5X^6+3X^3"
输出:
"-5X^6+7X^4+3X^3"
例二
输入:
"-7X^4+5X^6-3X^3+3X^3+1X^0"
输出:
"5X^6-7X^4+1X^0"
练习阶段:
中级
代码
/*---------------------------------------
* 日期:2015-07-07
* 作者:SJF0115
* 题目:一元多项式化简
* 来源:华为机试练习题
-----------------------------------------*/
#include <iostream>
#include <map>
#include <string>
#include <stack>
using namespace std;
// 整型转换为字符串
string Int2Str(int num){
string str = "";
if(num == 0){
str = "0";
return str;
}//if
while(num){
str.insert(str.begin(),num % 10 + '0');
num /= 10;
}//while
return str;
}
/******************************************************************************************************
Description : 对输入的一元多项式,进行同类项合并,输出处理后的一元多项式
Prototype : void OrderPolynomial (char* InputString, char* OutputString)
Input Param : char* InputString 输入多项式字符串
Output Param : char* OutputString 输出多项式字符串
Return Value : void
********************************************************************************************************/
void OrderPolynomial (char* InputString, char* OutputString){
if(InputString==NULL){
return;
}//if
// key 为 系数
map<int,int> Map;
int size = strlen(InputString);
char* str = InputString;
int index = 0;
while(index < size){
bool positive = true;
// 正负号
if(str[index] == '+' ){
++index;
}//if
else if(str[index] == '-'){
positive = false;
++index;
}//else
// 系数
int num = 0;
while(str[index] >= '0' && str[index] <= '9'){
num =num * 10+ str[index] - '0';
++index;
}//while
if(!positive){
num = -num;
}//if
//跳过X^
index += 2;
// 指数
int number = 0;
while(str[index] >= '0' && str[index] <= '9'){
number = number * 10+ str[index] - '0';
++index;
}//while
// 相同指数
map<int,int>::iterator ite = Map.find(number);
if(ite != Map.end()){
ite->second += num;
}//if
// 没有相同指数
else{
Map.insert(pair<int,int>(number,num));
}//else
}//while
map<int,int>::reverse_iterator ite = Map.rbegin();
index = 0;
bool isFirst = true;
while(ite != Map.rend()){
// 等于 0
if(ite->second == 0){
++ite;
continue;
}//if
// 大于 0
int num = ite->second;
if(ite->second > 0){
if(!isFirst){
OutputString[index++] = '+';
}//if
}//if
// 小于 0
else if(ite->second < 0){
OutputString[index++] = '-';
num = -num;
}//else
isFirst = false;
// 系数
string tmp = Int2Str(num);
for(int i = 0;i < tmp.size();++i){
OutputString[index++] = tmp[i];
}//for
OutputString[index++] ='X';
OutputString[index++] ='^';
// 指数
tmp = Int2Str(ite->first);
for(int i = 0;i < tmp.size();++i){
OutputString[index++] = tmp[i];
}//for
++ite;
}//while
OutputString[index]='\0';
//cout<<OutputString<<endl;
return;
}