孫嚴(yán) 唐山鋼鐵集團有限責(zé)任公司信息自動化部

前言

一元多項式由某一變元的不同次冪的若干表達式代數(shù)和組成，形如Pn=p0+p1x+p2x2+…+pnxn，共n+1 項。在計算機中，則可用一個線性表P 來表示：P=(p0+p1+p2，…，pn)，則每一項的指數(shù)i 隱含在其系數(shù)pi的序號里。若只對多項式進行求值等不改變多項式的系數(shù)和指數(shù)的運算，則應(yīng)采用類似于順序表的存儲結(jié)構(gòu)，否則應(yīng)采用鏈?zhǔn)酱鎯Ρ硎?。因為在通常的?yīng)用中，多項式的次數(shù)可能很高而且變化很大，使得順序存儲結(jié)構(gòu)的最大長度很難確定，可能存在對內(nèi)存空間的浪費。

1 表達式求值（順序棧實現(xiàn)）

基本算數(shù)表達式滿足1.先乘除，后加減；2.從左至右；3.先括號內(nèi)，后括號外；對于在計算機中，如何實現(xiàn)上述基本運算規(guī)則？參照20 世紀(jì)50 年代波蘭邏輯學(xué)家Jan Lukasiewicz 發(fā)明的后綴表達法，即逆波蘭表示。叫后綴的原因在于所有的符號都是在要運算數(shù)字的后面出現(xiàn)。例如對于“9+(3-1)*3+10/2”的中綴表達式，轉(zhuǎn)換為逆波蘭式為“9 3 1-3*+10 2/+”，這樣借助于計算機線性結(jié)構(gòu)的棧，即可完成求值過程，這樣逆波蘭式可從根本上解決先乘除后加減的運算順序問題，也可解決括號優(yōu)先的問題。

因此，要想讓計算機具有處理通常標(biāo)準(zhǔn)的中綴表達式的能力，最重要的就是兩步：1.將中綴表達式轉(zhuǎn)化為后綴表達式（棧用來進出運算的符號）。2.將后綴表達式進行運算得出結(jié)果（棧用來進出運算的操作數(shù)）。對于基本運算，“+-*/”的優(yōu)先性均低于“(”但高于“)”，當(dāng)依次進棧兩運算符相同時，先進棧的優(yōu)先級＞后進棧的。增設(shè)“#”為表達式結(jié)束符，作用類似于括號，均屬于表達式界限符，因此，在表達式左邊也虛設(shè)“#”構(gòu)成表達式的一對括號。當(dāng)棧中“(”與“)”“#”與“#”相遇時候優(yōu)先級相等，表示求值運算已經(jīng)完成。算法如下，其中Precede()為判斷運算符優(yōu)先級函數(shù)，In()為判斷輸入字符是否為算符OP，Operate()為二元運算函數(shù)。棧OPTR 寄存運算符，OPND寄存操作數(shù)或運算結(jié)果。

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 一元多項式的操作表示（單鏈表實現(xiàn)）

采用鏈?zhǔn)酱鎯Y(jié)構(gòu)有序單鏈表表示一元多項式，每個結(jié)點元素有兩個數(shù)據(jù)項，系數(shù)項和指數(shù)項。即Pn(x)=p1xa+p2xb+…+pmxm為m 項的一元多項式表示為的表形式。則抽象數(shù)據(jù)類型表示為：

Typedef struct{float coef；int expn；}term,ElemType；//系數(shù)為實型，指數(shù)為整型

Typedef Linklist polynomial；//用帶頭結(jié)點的有序鏈表表示多項式

要實現(xiàn)這種一元多項式線性鏈表的加法，依照加法運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成“和多項式”中的一項；對于兩個一元多項式中所有指數(shù)不相同的項，則分別復(fù)抄到“和多項式”中去。而“和多項式”鏈表中的結(jié)點無需另生成，而應(yīng)該從兩個多項式的鏈表中摘取。加法算法如下：

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 的頭結(jié)點

qa=NextPos(ha)；qb=NextPos(hb)；//qa 和qb 分 別 指 向Pa和Pb 中當(dāng)前結(jié)點(現(xiàn)為第1 個結(jié)點)

while(！ListEmpty(Pa)&&！ListEmpty(Pb)&&qa){// Pa 和Pb 均非空且ha 沒指向尾結(jié)點(qa！=0)

a=GetCurElem(qa)；b=GetCurElem(qb)；//a 和b 為 兩 表中當(dāng)前比較元素

switch(cmp(a,b)){

case -1：ha=qa；qa=NextPos(ha)；break；//多項式Pa 中當(dāng)前結(jié)點的指數(shù)值小，ha 和qa 均向后移1 個結(jié)點

case 0： qa-＞data.coef+=qb-＞data.coef； // 兩者的指數(shù)值相等，修改Pa 當(dāng)前結(jié)點的系數(shù)值

if(qa-＞data.coef==0){//刪除多項式Pa 中當(dāng)前結(jié)點

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 中剩余結(jié)點

DestroyPolyn(Pb)； /*銷毀Pb*/}//addpolyn

減法實際是將其中一個多項式的符號取負(fù)(*-1)，再做加法。兩個一元多項式相乘的算法，可以利用兩個一元多項式相加的算法來實現(xiàn)，因為乘法運算可以分解為一系列的加法運算。

3 結(jié)語

因此，要把一個表達式翻譯成正確求值的一個機器指令序列，或者直接對表達式求值，首先要能夠正確地解釋表達式?？梢允褂脙蓚€工作棧OPTR用以寄存運算符，OPND用以寄存操作數(shù)或運算結(jié)果。其中調(diào)用兩個操作函數(shù)，其中percede 是判斷運算符棧的棧頂運算符與讀入運算符之間有限關(guān)系的函數(shù)，operate 為進行二元運算的函數(shù)。線性結(jié)構(gòu)能很好的將運算表達式進行存儲轉(zhuǎn)化，實際時間復(fù)雜度主要取決于所定義的基本操作，而對于實際操作人員是完全隱匿透明的。