[华为机试练习题]71.一元多项式化简

题目

背景:

编程实现如下功能：对输入的一元多项式，进行同类项合并，并按指数降序排序，输出处理后的一元多项式。

说明：

1. 多项式由若干个单项式组成，单项式之间为加、减（+,-）关系。
2. 单项式指数字与字母幂的乘积构成的代数式。对一元多项式，字母只有一种。
3. 同类项合并指将多项式中指数相同的单项式，系数经过加减求和，合并为一个单项式。按指数降序指多项式中，单项式按指数从大到小顺序相连。

格式说明

一元多项式输入输出时以字符串形式表示，格式如下

1. 单项式之间用单个加减运算符相连，运算符：+,-
2. 单项式由系数、字母、指数标识符、指数依次直接相连组成，各部分均不能省略。
   系数：只由若干0到9数字字符组成（系数不等于0，且不以0开头）
   字母：X
   指数标识符：^
   指数：只由若干0到9数字字符组成（指数可等于0，不等于0时不以0开头）
3. 其他约定
   输入不为空串，输出若为0则以空串表示
   字符串中除以上字符，不包含空格等其他字符，字符串尾部以’\0’结束
   多项式中第一个单项式前加运算时省略+符号,减运算时有-符号

注意：输入多项式符合上述格式，无需检查；输出多项式格式由考生程序保证

规格

输入多项式满足如下规格，考生程序无需检查： 
–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;
}