基于線性結構表達式求值及一元多項式操作表示的研究

孫嚴 唐山鋼鐵集團有限責任公司信息自動化部

前言

一元多項式由某一變元的不同次冪的若干表達式代數和組成，形如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 為進行二元運算的函數。線性結構能很好的將運算表達式進行存儲轉化，實際時間復雜度主要取決于所定義的基本操作，而對于實際操作人員是完全隱匿透明的。