读入2个多项式和一个运算符(加号+,减号-,乘号*),计算多项式运算结果,并按照要求输出运算结果。
输入样例:
x+5x^2
*
-x+5x^2
输出样例:
运算结果是:
x + 5x^2
*
-x + 5x^2
= -x^2 + 25x^4
多项式的定义
由若干个单项式,通过 '+' 或 '-' 连接起来的式子。 例如:-x^2+3-5x^6 + x + 9 + x
单项式的基本格式为:
系数x^幂指数
例如:
5x^2 表示5倍的 x 平方
3x^-4 表示3倍的 x 的 -4 次方
一个单项式内部【不允许】有空白字符(空格或\t)。例如不允许:2 x^ 3
输入要求
1)当省略系数,则表示系数为 1。例如:x^3
2)当系数省略为减号时,则表示系数为 -1。例如:-x^3
3)当省略幂指数时,则表示幂指数为1。例如:-5x。
4)对于常数项,可以省略x^0,例如:-2 (表示 -2x^0)
单项输出要求
1)如果幂指数为 0,须简化为常数项。例如:3x^0 应该输出为 3
2)如果幂指数为 1,须省略它。例如:3x^1 应该输出为3x
3)如果系数为1或-1,须省略1。例如:-x^6,x^2
4)单项式内部不能有空白字符(空格或\t)
多项式输出要求
1)在项与项之间的+号、-号左右两侧须各留一个空格
2)按照幂指数升高的顺序输出,例如:-2 + 3x^5 -x^9
3)不输出系数为零的项
4)零多项式,输出 0
按照接口要求,编写以下 7 个函数代码
void PrintMonomial(int coef, int expo);
Monomial* ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);
函数接口定义:
------------------------------------------------------------------------------
函数 PrintMonomial - 输出单项式
void PrintMonomial(int coef, int expo);
1)如果幂指数为 0,则简化为常数项。例如:x^0 应该输出为 1
2)如果幂指数为 1,则须省略它。例如:-3x^1 应该输出为-3x
3)如果系数为1或-1,则输出时须省略1。例如:-x^6,x^2
4)输出时,单项式内部不能有空白字符(空格或\t)
5)零单项式不输出
参数
coef - 单项式系数
expo - 单项式幂指数
返回值
无
------------------------------------------------------------------------------
函数 ParseMonomial - 读入字符串中的第一个单项式
Monomial* ParseMonomial(char **s)
参数
s - *s是字符串指针,指定数据读取源
函数执行成功后,*s会单项式后面的第一个字符
返回值
成功 - 所读入的单项式指针
失败 - NULL
------------------------------------------------------------------------------
函数 InsertAfterTail - 插入新节点到多项式链表末尾
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
参数
head - 多项式的头节点指针
pNewNode - 新插入节点的指针
返回值
插入节点后,新多项式的头节点指针
------------------------------------------------------------------------------
函数 DeleteZeroTerms - 删除多项式中的零系数节点
Polynomial DeleteZeroTerms(Polynomial head);
参数
head - 被简化的多项式的头节点指针
返回值:简化后的多项式链表的节点指针
------------------------------------------------------------------------------
函数 SortPolynomial - 对多项式按照幂指数进行升序排序
Polynomial SortPolynomial(Polynomial head);
参数
head - 被排序的多项式的头节点指针
返回值:排序后的多项式头节点指针
------------------------------------------------------------------------------
函数 Minus - 多项式求差: p1 - p2
链表 p1和p2保持不变
Polynomial Minus(Polynomial p1, Polynomial p2);
返回值:
多项式 "差" 的表头指针
------------------------------------------------------------------------------
函数 Multiply - 多项式乘积: p1 * p2
链表 p1和p2保持不变
Polynomial Multiply(Polynomial p1, Polynomial p2);
返回值:
多项式 "积" 的表头指针
------------------------------------------------------------------------------
测试程序
#include <stdlib.h>
#include <stdio.h>
#define MAXLINE 1024
// 交换 a, b,以t为中间变量
#define SWAP(a,b,t) (t)=(a),(a)=(b),(b)=(t)
// 单项式结构
typedef struct MonomialStruct{
int coef; // 系数
int expo; // 幂次
struct MonomialStruct * next;
} Monomial;
// 多项式类型定义
typedef Monomial *Polynomial;
void PrintMonomial(int coef, int expo);
Monomial* ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);
/*******************************************************************************
函数 CreateMonomial - 创建一个单项式项式节点
Monomial * CreateMonomial(int coef, int expo);
参数
coef - 系数
expo - 幂指数
返回值
成功 - 所创建的节点指针
失败 - NULL
*******************************************************************************/
Monomial * CreateMonomial(int coef, int expo)
{
Monomial * p = (Monomial*)malloc(sizeof(Monomial));
if( !p )
return NULL;
p->coef = coef;
p->expo = expo;
p->next = NULL;
return p;
}
/*******************************************************************************
函数 DeletePolynomial - 删除一个多项式,并释放所有的节点内存
Polynomial DeletePolynomial(Polynomial p)
参数
head - 被删除的多项式的头节点指针
返回值
空指针 NULL
*******************************************************************************/
Polynomial DeletePolynomial(Polynomial head)
{
while(head) {
Monomial * d = head;
head = head->next;
free(d);
}
return NULL;
}
/*****************************************************
函数 AddMonomial - 在多项式中添加一个单项式
如果链表中已经存在同次项,则不会创建新节点,而是对系数进行累加。
Polynomial AddMonomial(Polynomial head, int coef, int expo);
参数
head - 多项式的头节点指针
coef - 单项式的系数
expo - 单项式的幂指数
返回值
新的多项式链表的表头指针
*****************************************************/
Polynomial AddMonomial(Polynomial head, int coef, int expo)
{
Monomial * p;
if( coef==0 )
return head;
for( p = head; p && p->expo!=expo; p = p->next )
; // 寻找同次项
if( p )
// 找到同次项
p->coef += coef;
else {
p = CreateMonomial(coef, expo);
head = InsertAfterTail(head, p);
}
return head;
}
/*****************************************************
函数 Add - 多项式求和: p1 + p2
链表 p1 和 p2保持不变
返回值:
多项式 "和" 的表头指针
*****************************************************/
Polynomial Add(Polynomial p1, Polynomial p2)
{
Polynomial h = NULL;
for( ; p1; p1=p1->next )
h = AddMonomial(h, p1->coef, p1->expo);
for( ; p2; p2=p2->next )
h = AddMonomial(h, p2->coef, p2->expo);
return h;
}
// 判断字符串 s 的起始字符是否为:x^ 或 X^
int IsEXPO(char *s)
{
return ( (s[0]=='x' || s[0]=='X') && s[1]=='^');
}
// 字符是否为\n或\0
int IsEndingChar(char ch)
{
return (ch==0 || ch=='\n');
}
// 跳过字符串起始部分的空格和制表符
// 返回值:一个指针
// 指向字符串前面的第一个非空白字符
char * SkipSpaceChars(char *s)
{
while( *s==' ' || *s=='\t' )
s++;
return s;
}
/*****************************************************
函数 GetSignChar - 字符串*s中第一个单项式的符号字符
int GetSignChar(char **s);
参数
s - *s是字符串指针
返回值
成功 -返回符号字符,将*s指向符号之后的字符
不成功 -返回 0
*****************************************************/
int GetSignChar(char **s)
{
char *p = SkipSpaceChars(*s); // 忽略空白字符
if( *p=='+' || *p=='-' ) {
*s = p + 1;
return (*p);
}
return 0;
}
/*****************************************************
从一行标准输入,读取一个一元多项式
返回值:
所读取的多项式链表的表头指针
*****************************************************/
Polynomial ParsePolynomial()
{
char linebuffer[1024], *s = linebuffer;
Polynomial hResult = NULL;
if( !fgets(linebuffer, sizeof(linebuffer), stdin) )
return NULL;
while( 1 ) {
Monomial *pNewNode;
int signChar = GetSignChar(&s);
pNewNode = ParseMonomial(&s);
if( !pNewNode )
break;
if( signChar == '-' )
pNewNode->coef = -pNewNode->coef;
hResult = InsertAfterTail(hResult, pNewNode);
}
return hResult;
}
/*****************************************************
函数 PrintPolynomial - 输出多项式
Polynomial PrintPolynomial(Polynomial pHead);
两个单项式之间的+/-左右各留出一个空格
返回值
被输出的多项式
*****************************************************/
Polynomial PrintPolynomial(Polynomial pHead)
{
Polynomial p = pHead;
int firstTerm = 1, nothingOutputYet = 1;
for( ; p; p = p->next )
{
int c = p->coef;
int k = p->expo;
if( c==0 ) // 忽略系数为0的项
continue;
if( firstTerm ) {
PrintMonomial(c,k);
firstTerm = 0;
} else {
printf(" %c ", c>0 ? '+' : '-');
PrintMonomial(c>0?c:-c, k);
}
nothingOutputYet = 0;
}
if( nothingOutputYet )
putchar('0');
putchar('\n');
return pHead;
}
/*------------------------------------------------------------------
1. 如果测试多项式输入输出,那么:
输入多项式1,回车
回车
2. 如果测试两个多项式的 "加"、"减"、"乘"运算,那么:
输入第一个多项式,回车
输入运算符(+、-、*),回车
输入第二个多项式,回车
------------------------------------------------------------------*/
int main()
{
Polynomial p1, p2, pResult;
char cmdString[MAXLINE], cmd;
p1 = ParsePolynomial(); //读入多项式 1
if( !fgets(cmdString, sizeof(cmdString), stdin) )
return 0;
cmd = cmdString[0];
if( cmd!='+' && cmd!='-' && cmd!='*' ) {
//测试多项式的输入和输出
printf("input=");
PrintPolynomial( p1 );
return 0;
}
p2 = ParsePolynomial(); //读入多项式 1
// printf("\n运算结果是:\n\n");
PrintPolynomial( p1 );
printf("%c\n", cmd);
PrintPolynomial( p2 );
printf("=\n");
if( cmd=='+' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Add(p1,p2) ) ) );
else if( cmd=='-' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Minus(p1, p2) ) ) );
else //if( cmd=='*' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Multiply(p1, p2) ) ) );
// printf("\n");
DeletePolynomial(p1);
DeletePolynomial(p2);
DeletePolynomial(pResult);
return 0;
}