基于線性結(jié)構(gòu)表達(dá)式求值及一元多項(xiàng)式操作表示的研究

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

前言

一元多項(xiàng)式由某一變?cè)牟煌蝺绲娜舾杀磉_(dá)式代數(shù)和組成，形如Pn=p0+p1x+p2x2+…+pnxn，共n+1 項(xiàng)。在計(jì)算機(jī)中，則可用一個(gè)線性表P 來(lái)表示：P=(p0+p1+p2，…，pn)，則每一項(xiàng)的指數(shù)i 隱含在其系數(shù)pi的序號(hào)里。若只對(duì)多項(xiàng)式進(jìn)行求值等不改變多項(xiàng)式的系數(shù)和指數(shù)的運(yùn)算，則應(yīng)采用類似于順序表的存儲(chǔ)結(jié)構(gòu)，否則應(yīng)采用鏈?zhǔn)酱鎯?chǔ)表示。因?yàn)樵谕ǔ５膽?yīng)用中，多項(xiàng)式的次數(shù)可能很高而且變化很大，使得順序存儲(chǔ)結(jié)構(gòu)的最大長(zhǎng)度很難確定，可能存在對(duì)內(nèi)存空間的浪費(fèi)。

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

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

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

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

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

Typedef Linklist polynomial；//用帶頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式

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

void AddPolyn(polynomial &Pa,polynomial &Pb){//多項(xiàng)式加法：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb

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

ha=GetHead(Pa)；hb=GetHead(Pb)；//ha 和hb 分 別指向Pa和Pb 的頭結(jié)點(diǎn)

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

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

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

switch(cmp(a,b)){

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

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

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

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é)點(diǎn)

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

減法實(shí)際是將其中一個(gè)多項(xiàng)式的符號(hào)取負(fù)(*-1)，再做加法。兩個(gè)一元多項(xiàng)式相乘的算法，可以利用兩個(gè)一元多項(xiàng)式相加的算法來(lái)實(shí)現(xiàn)，因?yàn)槌朔ㄟ\(yùn)算可以分解為一系列的加法運(yùn)算。

3 結(jié)語(yǔ)

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