基于线性结构表达式求值及一元多项式操作表示的研究

孙严 唐山钢铁集团有限责任公司信息自动化部

前言

一元多项式由某一变元的不同次幂的若干表达式代数和组成，形如Pn=p0+p1x+p2x2+…+pnxn，共n+1 项。在计算机中，则可用一个线性表P 来表示：P=(p0+p1+p2，…，pn)，则每一项的指数i 隐含在其系数pi的序号里。若只对多项式进行求值等不改变多项式的系数和指数的运算，则应采用类似于顺序表的存储结构，否则应采用链式存储表示。因为在通常的应用中，多项式的次数可能很高而且变化很大，使得顺序存储结构的最大长度很难确定，可能存在对内存空间的浪费。

1 表达式求值（顺序栈实现）

基本算数表达式满足1.先乘除，后加减；2.从左至右；3.先括号内，后括号外；对于在计算机中，如何实现上述基本运算规则？参照20 世纪50 年代波兰逻辑学家Jan Lukasiewicz 发明的后缀表达法，即逆波兰表示。叫后缀的原因在于所有的符号都是在要运算数字的后面出现。例如对于“9+(3-1)*3+10/2”的中缀表达式，转换为逆波兰式为“9 3 1-3*+10 2/+”，这样借助于计算机线性结构的栈，即可完成求值过程，这样逆波兰式可从根本上解决先乘除后加减的运算顺序问题，也可解决括号优先的问题。

因此，要想让计算机具有处理通常标准的中缀表达式的能力，最重要的就是两步：1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。2.将后缀表达式进行运算得出结果（栈用来进出运算的操作数）。对于基本运算，“+-*/”的优先性均低于“(”但高于“)”，当依次进栈两运算符相同时，先进栈的优先级＞后进栈的。增设“#”为表达式结束符，作用类似于括号，均属于表达式界限符，因此，在表达式左边也虚设“#”构成表达式的一对括号。当栈中“(”与“)”“#”与“#”相遇时候优先级相等，表示求值运算已经完成。算法如下，其中Precede()为判断运算符优先级函数，In()为判断输入字符是否为算符OP，Operate()为二元运算函数。栈OPTR 寄存运算符，OPND寄存操作数或运算结果。

EvaluateExpression(){

InitStack(OPTR)；Push(OPTR,'#')；InitStack(OPND)；c=get char()；

Whi le(c！='#'||GetTop(OPTR)！='#'){if(！In(c,OP)){Push(OPND,c)；c=getchar()；}

else switch(Precede(GetTop(OPTR),c)){

case'＜'：Push(OPTR,c)；c=getchar()；break；

case'='：Pop(OPTR,x)；c=getchar()；break；

case'＞'：Pop(OPTR,z)；Pop(OPND,b)；Pop(OPND,a)；Push(O PND,Operate(a,z,b))；break；}

}return GetTop(OPND)；}

2 一元多项式的操作表示（单链表实现）

采用链式存储结构有序单链表表示一元多项式，每个结点元素有两个数据项，系数项和指数项。即Pn(x)=p1xa+p2xb+…+pmxm为m 项的一元多项式表示为的表形式。则抽象数据类型表示为：

Typedef struct{float coef；int expn；}term,ElemType；//系数为实型，指数为整型

Typedef Linklist polynomial；//用带头结点的有序链表表示多项式

要实现这种一元多项式线性链表的加法，依照加法运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。而“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。加法算法如下：

void AddPolyn(polynomial &Pa,polynomial &Pb){//多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb

Position ha,hb,qa,qb；term a,b；

ha=GetHead(Pa)；hb=GetHead(Pb)；//ha 和hb 分 别指向Pa和Pb 的头结点

qa=NextPos(ha)；qb=NextPos(hb)；//qa 和qb 分 别 指 向Pa和Pb 中当前结点(现为第1 个结点)

while(！ListEmpty(Pa)&&！ListEmpty(Pb)&&qa){// Pa 和Pb 均非空且ha 没指向尾结点(qa！=0)

a=GetCurElem(qa)；b=GetCurElem(qb)；//a 和b 为 两 表中当前比较元素

switch(cmp(a,b)){

case -1：ha=qa；qa=NextPos(ha)；break；//多项式Pa 中当前结点的指数值小，ha 和qa 均向后移1 个结点

case 0： qa-＞data.coef+=qb-＞data.coef； // 两者的指数值相等，修改Pa 当前结点的系数值

if(qa-＞data.coef==0){//删除多项式Pa 中当前结点

DelFirst(Pa,ha,qa)；FreeNode(qa)；}

else ha=qa；DelFirst(Pb,hb,qb)；FreeNode(qb)；qb=NextPos(hb)；qa=NextPos(ha)；break；

case 1： DelFirst(Pb,hb,qb)；InsFirst(Pa,ha,qb)；ha=ha-＞next；qb=NextPos(hb)；} //switch

} //while

if(！ListEmpty(Pb)){

Pb.tail=hb；Append(Pa,qb)；}//链接Pb 中剩余结点

DestroyPolyn(Pb)； /*销毁Pb*/}//addpolyn

减法实际是将其中一个多项式的符号取负(*-1)，再做加法。两个一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。

3 结语

因此，要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确地解释表达式。可以使用两个工作栈OPTR用以寄存运算符，OPND用以寄存操作数或运算结果。其中调用两个操作函数，其中percede 是判断运算符栈的栈顶运算符与读入运算符之间有限关系的函数，operate 为进行二元运算的函数。线性结构能很好的将运算表达式进行存储转化，实际时间复杂度主要取决于所定义的基本操作，而对于实际操作人员是完全隐匿透明的。