樹與二叉樹1_習(xí)題與解答

1、1、括號的匹配（表達(dá)式的合法性檢查） 問題描述 假設(shè)一個表達(dá)式有英文字母（小寫）、運算符（ +， * ， /）和左右小達(dá)式的結(jié)束符。請編寫一個程序檢查表達(dá)式中的左右圓括號是否匹配，若匹配，“NO。假設(shè)表達(dá)式長度小于 255，左圓括號少于20個。圓）括號構(gòu)成，以“ ”作為表YES;否則返回則返回“ 問題分析 假設(shè)輸入的字符串存儲在 c 中（ var c:string255）。我們可以定義一個棧： vars:array1.maxnofchar;top:integer; 用它來存放表達(dá)式中從左往右的左圓括號（ 算法的思路為：順序（從左往右）掃描表達(dá)式的每個字符maxn=20)。ci到的是“）”，則讓

2、棧頂元素出棧;當(dāng)棧發(fā)生下溢或當(dāng)表達(dá)式處理完畢而棧非空時，都表示不匹配，返回 “ NO ;否則表示匹配，返回“，若是“（”，則讓它進棧；若遇YES”。 參考程序 program lx5;const maxn=20;var c:string;function judge(c:string):boolean;var s:array1.maxnofchar;top,i:integer;ch:char;beginjudge:=true;top:=0;i:=1;ch:=ci;while ch dobeginif (ch=()or(ch=) thencase choft end;end;i:=i+1;ch:

3、=ci;end;()begin top:=top+1;stop:=( if top0 then top:=top-1end;else begin judge:=false;exiiftop0 thenjudge:=false;end;mainbeginassign(input,match.in);assign(output,match.out);reset(input); rewrite(output); readln(c);else writeln(NO);if judge(c) then writeln(YES) close(input);close(output);end.2、編程把中綴

4、表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 問題描述 輸入一個中綴表達(dá)式，編程輸出其后綴表達(dá)式，要求輸出的后綴表達(dá)式的運算次序與輸入的中綴表達(dá)式的 運算次序一致。為簡單起見，假設(shè)輸入的中綴表達(dá)式由（加）、（減）、*（乘）、（除）四個運算233。符號以及左右圓括號和大寫英文字母組成，其中算術(shù)運算符遵守先乘除后加減的運算規(guī)則。假設(shè)輸入的中 綴表達(dá)式長度不超過 80 個字符，且都是正確的，即沒有語法錯誤，并且凡出現(xiàn)括號其內(nèi)部一定有表達(dá)式， 即括號內(nèi)部至少有一個運算符號。以下是一個運行實例 樣例輸入 X+A*( Y-B)-Z/F 樣例輸出 XAYB-*+ZF/-，用來分別存放表達(dá)式中的操作數(shù)和運算符。開始時操#號，并在表

5、達(dá)式的末尾相應(yīng)地加上一個 #號，并規(guī)f 就是用來存 算法設(shè)計 設(shè)置兩個棧：操作數(shù)棧（ ovs ）和運算符棧（ ops） 作數(shù)棧為空，運算符棧中放入一個特殊的標(biāo)志運算符號 定#號的優(yōu)先級最低，然后從左向右掃描表達(dá)式，凡遇操作數(shù)便一律進棧；若遇運算符，則判斷其優(yōu)先級是 否大于運算符棧棧頂元素的優(yōu)先級。若小，則棧頂運算符退棧，并從操作數(shù)棧中彈出兩個操作數(shù)（操作數(shù) 為后綴表達(dá)式）進行后綴變換處理，處理結(jié)果進操作數(shù)棧，重復(fù)剛才的比較，直到棧頂運算符的優(yōu)先級大 于等于當(dāng)前運算符的優(yōu)先級； 此時， 若當(dāng)前運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級， 則當(dāng)前運算符進棧， 繼續(xù)掃描；若當(dāng)前運算符的優(yōu)先級等于棧頂運算符

6、的優(yōu)先級，則彈出棧頂運算符，繼續(xù)掃描。掃描完該表 達(dá)式后運算符棧為空，操作數(shù)棧中只有一個元素，該元素就是所要求的后綴表達(dá)式。 上圖是對范例表達(dá)式的掃描示意圖。 這樣，我們需要事先把所有運算符號的優(yōu)先級定義并存放好，這很簡單，以下程序中的數(shù)組放運算符之間的優(yōu)先級關(guān)系的。 1（） 表示前面的運算符優(yōu)先于后面的運算符， -1（） 表示后面的運算符優(yōu)先 于前面的運算符，0（=）表示前面的運算符的優(yōu)先級與后面的運算符相同，2（ERROR表示這兩個運算符如果在掃描中相遇的話，意味著該表達(dá)式是錯誤的。需要補充的是： 左括號的優(yōu)先級是最高的， 而里層的左括號比外層的左括號更優(yōu)先， 右括號的優(yōu)先級是除 # 號以

7、外最低的，但左括號和右括號的優(yōu)先級則是相等的，這樣定義的目的是為了消去括號。以上規(guī)律列表如下：- */(ERROR #ERROR = 參考程序 program lx6(input,output);const max=100;op_set:setof char=+,-,*,/;letter:setof char=A.Z;var expression,result:string;procedure scan(expression:string);var i,top1,top2:integer;ovs:array1.maxops:array1.maxofofstringmax;char;beginf

8、:array#./,#./of shortint;f+,+:=1;f+,-:=1;f+,*:=-1;f+,/:=-1;f+,(:=-1;+,):=1;f+,#:=1;f-,+:=1;f-,-:=1;f-,*:=-1;f-,/:=-1;f-,(:=-1;-,):=1;f*,+:=1;f-,#:=1;f*,-:=1;f*,*:=1;f*,/:=1;f*,(:=-1;f*,):=1;f*,#:=1;1;f/,+:=1;f/,):=1;f/,-:=1; f/,#:=1;f/,*:=1;f/,/:=1;f/,(:=-f(,+:=-1;f(,-:=-1;f(,*:=-1;f(,/:=-1;f(,(:=-1

9、;f(,):=0;f(,#:=2;f),+:=2;f),-:=2;f),*:=2;f),/:=2;f),():=2;f),):=2;f),#:=2;f#,+:=-1;f#,-:=-1;f#,*:=-1;f#,/:=-1;f#,(:=-1;f#,):=2; f#,#:=0;expression:=expression+#;ops1:=#;top1:=0;top2:=1;fori:=1to length(expression)do 逐個掃描 beginifexpressioniinletter 是字母就進棧 then begin top1:=top1+1;ovstop1:=expressionie

10、ndelsebegin 運算符 while fopstop2,expressioni=1do 棧頂運算符優(yōu)先級高于當(dāng)前運算符 begin 取棧頂上面的兩個元素運算后，再壓棧 ovstop1-1:=ovstop1-1+ovstop1+opstop2;top1:=top1-1;top2:=top2-1end;if fopstop2,expressioni=0then top2:=top2-1優(yōu)先級相同，則抵消 else begin top2:=top2+1; 棧頂運算符優(yōu)先級低于當(dāng)前運算符，則壓棧 opstop2:=expressioniend;endend;result:=ovs1 返回結(jié)果 e

11、nd;beginmainwrite(Inputexpression:);readln(expression);scan(expression);writeln(The result is: ,result)end.3、編程求一個后綴表達(dá)式的值 問題描述 從鍵盤讀入一個后綴表達(dá)式（字符串），只含有 0-9 組成的運算數(shù)及加（ +）、減（）、乘（ * ）、除（ / ） 四種運算符。每個運算數(shù)之間用一個空格隔開，不需要判斷給你的表達(dá)式是否合法。以作為結(jié)束標(biāo)志。 問題分析 后綴表達(dá)式的處理過程很簡單，過程如下：掃描后綴表達(dá)式，凡遇操作數(shù)則將之壓進堆棧，遇運算符則從 堆棧中彈出兩個操作數(shù)進行該運算，將運

12、算結(jié)果壓棧，然后繼續(xù)掃描，直到后綴表達(dá)式被掃描完畢為止， 此時棧底元素即為該后綴表達(dá)式的值。比如，16-9*（4+3）轉(zhuǎn)換成后綴表達(dá)式為：16口 9口 4口 3 +* -，在字符數(shù)組 A中的形式為:棧中的變化情況：運行結(jié)果：-47 參考程序1programlx7_1;const maxn=20;var stack:array1.maxnof integer;s:string;function comp(s:string):integer;var ch:char;i,top,x,y,z:integer;begintop:=0;i:=1;ch:=si;while i=length(s) do be

13、gin case ch of0.9:beginx:=0;while chdo beginx:=x*10+ord(ch)-ord(0);i:=i+1;ch:=si;end;top:=top+1; stacktop:=x;end;+:begin x:=stacktop;top:=top-1;y:=stacktop;z:=y+x;stacktop:=zend;:begin x:=stacktop;top:=top-1;y:=stacktop;z:=y-x;stacktop:=zend;1*1:beginx:=stacktop;top:=top-1;y:=stacktop;z:=y*x;stackto

14、p:=z end;/:beginx:=stacktop;top:=top-1;y:=stacktop;z:=y div x;stacktop:=z end;end;i:=i+1;ch:=si;end;while comp:=stacktop;end;beginmaina string(_over):);writeln(inputend.readln(s);writeln(result=,comp(s);readln; 參考程序 2programlx7_2;typestack=recorddata ： array1100 ofreal ； 存放實型數(shù) varend；s ： stack ； ch：

15、char ；top ：0 .100；i ： integer ； x:real;a:array1.30ofchar;functionpop(vars： stack):real ；出棧beginpop:=s.datas.top;s.top:=s.top-1 ；end；procedure push(var s： stack ；x：real);入棧begins.top:=s.top+1s.datas.top:=xend；begin 主程序 whilebeginwhilei:=0;repeati:=i+1;read(ai); 將表達(dá)式存入數(shù)組 auntilai= ;s.top:=0;i:=1;ch:=a

16、i;chchdocase ch0doofx:=x*10+ord(ch)-ord(i:=i+1;ch:=ai;清空棧i 為 a 數(shù)組的下標(biāo) . 9 : begin 產(chǎn)生完整的數(shù) x:=0;begin0);end;end;+x:=pop(s)+pop(s)beginbegin x:=pop(s);x:=pop(s)-x;end;x:=pop(s)*pop(s);/begin x:=pop(s);x:=pop(s)/x;end;end;push(s,x);i:=i+1;ch:=ai;將上面得到的 x 入棧 繼續(xù)掃描 a 數(shù)組 end;writeln(pop(s)end.4、計算后綴表達(dá)式的值編一個程

17、序，輸入一個實數(shù)中綴表達(dá)式（由 0-9 組成的運算數(shù)、加（ +）、減（ - ）、乘（ * ）、除（ / ）四種運算符、左右小括號、小數(shù)點組成。注意“- ”也可作為負(fù)數(shù)的標(biāo)志），判斷表達(dá)式是否合法，如果不合法，請輸出“ NO ;否則求出后綴表達(dá)式的值并輸出。注意：必須用棧操作，不能直接輸出表達(dá)式的值；必須寫成 8* （-5 ）； 12.和.5 也算合法，分別表示 12.0 和 0.5；8*-5 是不合法的， 參考程序 program lx8; const max=100;list_1:setofchar=*,/,+,-,.,(,),0.9;list_2:setofchar=*,/,+,-;num

18、ber:setofchar=0.9;zero=0.0000000001;var sin,tmp:string;result:real;procedureouterror;beginwriteln(No);halt;end;functionerror(s:string):boolean;var i,j,k:longint;f:boolean;beginf:=false;k:=0;for i:=1 to length(s) doifnot(si in list_1) then f:=true;if(si in list_2)and(si-1inlist_2) then f:=true;if(si=

19、()and(si-1=)then f:=true;ifsi=(then inc(k);ifsi=)then dec(k);end;if k0 thenf:=true;error:=f;end;procedure dealwithnegative(var var i,j,k:longint;s:string);begintmp:string;tmp:=;i:=1;for i:=1 tolength(s)dobeginif(si=-)and(i=1)or(si-1=()thentmp:=tmp+0;tmp:=tmp+si;end;functionvarr:real;end;begins:=tmp;

20、convert(s:string;var i:longint):real;tmp:string;p:longint;tmp:=;while(siinnumber)or(si=.)dobegintmp:=tmp+si;inc(i);end;i:=i-1;val(tmp,r,p);if p0 then outerror;convert:=r;end;functioncalc(r1,r2:real;ch:char):real;begincasechof+:calc:=r1+r2;-:calc:=r1-r2;*:calc:=r1*r2;/:beginif abs(r2)zerothen beginwr

21、iteln(dividedby zero);halt;end;calc:=r1/r2;end;end;end;result:real);procedure scan(sin:string;varvar i,j,top1,top2:longint;ovs:array1.maxofreal;ops:array1.max ofchar;f:array#./,#./oflongint;beginf+,+:=1;f+,-:=1;f+,*:=-1;f+,/:=-1;f+,(:=-1;f+,):=1;f-,+:=1;f-,-:=1;f-,*:=-1;f-,/:=-1;f-,(:=-1;f-,):=1;f*,

22、+:=1;f*,-:=1;f*,*:=1;f*,/:=1;f*,(:=-1; f*,):=1;f/,+:=1;f/,-:=1;f/,*:=1;f/,/:=1;f/,(:=-1; f/,):=1;f(,+:=-1;f(,-:=-1;f(,*:=-1;f(,/:=-1;f(,(:=-1;f(,):=0;if error(sin) then outerror;dealwithnegative(sin);sin:=sin+);ops1:=(;top1:=0; top2:=1;i:=1;whilei=length(sin)dobeginif(siniinnumber)or(sini=.)thenbegi

23、ntop1:=top1+1;ovstop1:=convert(sin,i);endelsebegindowhile fopstop2,sini=1ovstop1-1:=calc(ovstop1-1,ovstop1,opstop2);top 1:=t op 1-1;top 2:=t op 2-1;end;iffop st op 2,sini=0then top 2:=to p2-1else begintop 2:=to p2+1; op st op 2:=sini; end;end;inc(i);end;result:=ovs1;end;begin main write(l nput readl

24、n(sin); scan(sin,result); writeln(Thea exp ression:);result is: ,result:0:3);end.5、單詞查找樹問題描述在進行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表里。 為了提高查找和定位的速度，通常都畫出與單詞列表所對應(yīng)的單詞查找樹，其特點如下：1. 根結(jié)點不包含字母，除根結(jié)點外每一個結(jié)點都僅包含一個大寫英文字母；2. 從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié) 點對應(yīng)的單詞。單詞列表中的每個單詞，都是該單詞查找樹某個結(jié)點所對應(yīng)的單詞；3. 在滿足上述條件下，該單詞查找樹的結(jié)點數(shù)最

25、少。4. 例如圖6_2左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。注意，對一個確定的單詞 列表，請統(tǒng)計對應(yīng)的單詞查找樹的結(jié)點數(shù)（包含根結(jié)點）問題輸入輸入文件名為 word.in，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行 回車符。每個單詞僅由大寫的英文字母組成，長度不超過 32K,至少有一行數(shù)據(jù)。問題輸出輸出文件名為 word.out ,該文件中僅包含一個整數(shù)， 找樹的結(jié)點數(shù)。/63個字母。文件總長度不超過該整數(shù)為單詞列表對應(yīng)的單詞查樣例輸入AANASPASA ANASP ASASC ASCIIBAS BASICASCASCIIBASBASIC樣例輸出13算法分析首先要對建樹的過程有一個

26、了解。對于當(dāng)前被處理的單詞和當(dāng)前樹：在根結(jié)點的子結(jié)點n位及其中找單詞的第一位字母，若存在則進而在該結(jié)點的子結(jié)點中尋找第二位如此下去直到單 詞結(jié)束，即不需要在該樹中添加結(jié)點；或單詞的第n位不能被找到，即將單詞的第2從第N可見，后的字母依次加入單詞查找樹中去。但，本問題只是問你結(jié)點總數(shù)，而非建樹方案，且有 32K文件，所以應(yīng)該考慮能不能通過不建樹就直接算出結(jié)點數(shù)？為了說明問題的本質(zhì)，我們 給出一個定義：一個單詞相對于另一個單詞的差：設(shè)單詞1的長度為L,且與單詞位開始不一致，則說單詞1相對于單詞2的差為L-N+1，這是描述單詞相似程度的量。 將一個單詞加入單詞樹的時候，須加入的結(jié)點數(shù)等于該單詞樹中已

27、有單詞的差的最小值。單詞的字典順序排列后的序列則具有類似的特性，即在一個字典順序序列中，第m個單詞相對于第m-1個單詞的差必定是它對于前m-1個單詞的差中最小的。 于是，得出建樹的等效算法：讀入文件；對單詞列表進行字典順序排序；依次計算每個單詞對前一單詞的差，并把差累加起來。注意：第一個單詞相對于“空”的差為該單詞的長度； 累加和再加上1 （根結(jié)點），輸出結(jié)果。 就給定的樣例，按照這個算法求結(jié)點數(shù)的過程如下表：表6 1原單詞列表排序后的列表差值A(chǔ)A1ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2總計12輸出13當(dāng)然應(yīng)數(shù)據(jù)結(jié)構(gòu)先確定32

28、K（ 32*1024=32768字節(jié)）的文件最多有多少單詞和字母。該盡可能地存放較短的單詞。因為單詞不重復(fù)，所以長度為1的單詞（單個字母）最多 26個；長度為2的單詞最多為26*26=676個；因為每個單詞后都要一個換行符（換行符在計算機中占2個字節(jié)），所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié)；剩余字節(jié)（32768-2782=29986字節(jié)）分配給長度為3的單詞（長度為3的單詞最多有26*26*26=17576 個）有 29986/ （ 3+2） 5997。所以單詞數(shù)量最多為 26+676+5997=6699。定義一個數(shù)組：a： array1.32767 o

29、f char;把所有單詞連續(xù)存放起來，文件中每個 單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個“空格”字符。這樣既省略了一個存放單詞長度的數(shù)組，又方便且節(jié)省了一點空間。另外為了排序，再設(shè)一個數(shù)組 integer ；存放每個單詞在 a 中的起始位置。這樣，排序時用 值就可以了。 參考程序 Program p6_1(Input, Output) ；Varindex:array1. 6700 of a 比較，但只要交換 index 的a:Array1.32767 Of Char；index:Array1.6700 Of Integer；n,k,i,j,tot,t:Integer；s,pre,now:String ；Function cmp(i, j:Longint):Boolean ； 比較從 ai 開始