棧和隊(duì)列修改稿.ppt

1、1,棧和隊(duì)列,JSOI2010冬令營(yíng)第4講,2,一、棧的概念和特性,回顧線性表的特性： 除了首尾結(jié)點(diǎn)，所有的結(jié)點(diǎn)都有前驅(qū)和后繼； 首結(jié)點(diǎn)只有后繼沒(méi)有前驅(qū)，尾結(jié)點(diǎn)只有前驅(qū)沒(méi)有后繼； 線性表的任何位置都可以進(jìn)行插入刪除等操作。 現(xiàn)在我們對(duì)線性表的操作做一點(diǎn)限制，規(guī)定所有的插入或刪除操作只能在線性表的一端進(jìn)行，這樣的線性表稱為棧（stack）。 棧是一種特殊的線性表，對(duì)它的插入和刪除都限制在表的同一端進(jìn)行。,3,一、棧的概念和特性,把可以操作的一端稱為棧頂，不允許操作的一端稱為棧底。在棧頂插入一個(gè)元素，稱為進(jìn)棧，在棧頂刪除一個(gè)元素稱為出棧。 棧中元素的進(jìn)出是按后進(jìn)先出的原則進(jìn)行，這是棧結(jié)構(gòu)的重要特征

2、。 （LIFO:Last In First Out） 用一個(gè)變量記錄棧頂?shù)奈恢?，通常稱這個(gè)變量為棧指針。,4,練習(xí)4.1,設(shè)棧S的初始狀態(tài)為空,現(xiàn)有5個(gè)元素組成的序列1,2,3,4,5,對(duì)該序列在S 棧上依次進(jìn)行如下操作(從序列中的1開(kāi)始,出棧后不再進(jìn)棧):進(jìn)棧,進(jìn)棧,進(jìn)棧,出棧,進(jìn)棧,出棧,進(jìn)棧,問(wèn)： 出棧的元素序列是:_, 棧頂指針的值為_(kāi)， 棧頂元素為:_。,解答： 出棧序列為3，4， 棧頂指針值為3， 棧頂元素為5。,1,2,3,3,4,4,5,5,練習(xí)4.2,設(shè)棧S初始狀態(tài)為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過(guò)棧S，若出棧后的輸出順序?yàn)閑 2 ，e

3、 4 ，e 3 ，e 6 ，e 5 ，e 1 ，則棧S的容量至少應(yīng)該為（ ）。 A）2 B）3 C）4 D）5,e 1,e 2,e 2,e 3,e 4,e 4,e 3,e 5,e 6,e 6,e 5,e 1,6,練習(xí)4.3,若已知一個(gè)棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( )。 A)i B)n-1 C)n-i+1 D)不確定,【分析】 1， 2， 3， n P1，P2，P3，Pn 已知 p1=n，說(shuō)明所有的元素進(jìn)棧以后，才開(kāi)始出棧。所以p2=n-1，pi=n-i+1。,7,二、棧的存儲(chǔ)結(jié)構(gòu),順序棧 type arraytype= array1.

4、 n of datatype; var stack:arraytype; top:integer; 使用一維數(shù)組stack作為棧的存儲(chǔ)結(jié)構(gòu) n是棧的容量，即棧中最多可存放的元素 top是棧指針，top0，表示?？?，topn，表示棧滿；topn或者top0，則棧溢出,top=4,n,8,三、棧的主要運(yùn)算,在使用棧之前，首先需要將棧初始化； 往棧頂加入一個(gè)新元素，稱進(jìn)棧（壓棧）； 刪除棧頂元素，稱出棧（退棧、彈出）； (4)在使用棧的過(guò)程中，還要不斷測(cè)試棧是否為空或已滿，稱為測(cè)試棧。,9,三、棧的主要運(yùn)算,（1）棧的初始化操作（棧置空） top：0 （2）判斷?？蘸瘮?shù) function sempt

5、y(stack:arraytype):boolean; begin sempty:=(top=0); end; （3）判斷棧滿函數(shù) function sfull(stack:arraytype):boolean; begin sfull:=(top=n); end;,10,三、棧的主要運(yùn)算,（4）進(jìn)棧的操作過(guò)程（壓棧push） procedure push(x:integer); begin if sfull(stack) then writeln(Stack full!) else begin top:=top+1; stacktop:= x end end;,11,三、棧的主要運(yùn)算,（6）

6、出棧操作過(guò)程（pop） function pop:integer; begin if sempty(stack) then begin writeln(Stack empty!); end else begin pop:=stacktop; top:=top-1 end end;,12,四、棧的應(yīng)用,1、簡(jiǎn)單應(yīng)用：將十進(jìn)制數(shù)N轉(zhuǎn)換成r進(jìn)制的數(shù)。 其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法： 以M=3456，r=8為例轉(zhuǎn)換方法如下： M M / 8（整除） M % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高 所以：（3456）10 =（6563）8,13,程序,var s

7、:array0.100 of integer; top,x,r,i:integer; begin readln(x,r); for i:=1 to 100 do si:=0; top:=0; while x0 do begin top:=top+1; stop:=x mod r; x:=x div r; end; while top0 do begin write(stop); toP:=top-1; end; readln; end.,14,begin Readln(m,r); top:=0; While m0 do Begin push(m mod r); m:=m div r; End;

8、 While(not sempty(stack) ) do write(pop); end.,15,四、棧的應(yīng)用,例4. 1：程序員輸入問(wèn)題 程序員輸入程序，出現(xiàn)差錯(cuò)時(shí)可以采取以下的補(bǔ)救措施：敲錯(cuò)了一個(gè)鍵時(shí)，可以補(bǔ)敲一個(gè)退格符“”，以表示前一個(gè)字符無(wú)效；發(fā)現(xiàn)當(dāng)前一行有錯(cuò)，可以敲入一個(gè)退行符“”，以表示“”與前一個(gè)換行符之間的字符全部無(wú)效。 如：在終端上輸入了這樣兩行字符 PRKJOGRANMLX； VARCONSTN：10； 則實(shí)際有效的是： PROGRAMLX； CONSTN10；,16,例4. 1：程序員輸入問(wèn)題,【分析】 通過(guò)棧操作模擬程序員的輸入過(guò)程；逐行處理，處理完一行以后輸出結(jié)果，

9、棧置空； 逐字讀入數(shù)據(jù)，對(duì)每個(gè)讀入的字符進(jìn)行如下操作： 既不是退格符也不是退行符，則將該字符插入棧頂；是退格符，則從棧頂刪去一個(gè)字符； 是退行符 ，就把字符棧清為空棧。 PRKJOGRANMLX； VARCONSTN：10；,PROGRAMLX；,CONSTN10；,17,例4. 1：程序員輸入問(wèn)題,【數(shù)據(jù)結(jié)構(gòu)】 type stack=array1.100 of char; var s:stack; top:0.100; ch:char; i:integer;,棧,棧指針,18,例4. 1：程序員輸入問(wèn)題,置棧為空 procedure setnull(var s:stack); begin t

10、op:=0 end; 出棧 procedure pop(var s:stack); begin if top=0 then writeln(underflow) else top:=top -1; end;,19,例4. 1：程序員輸入問(wèn)題,入棧 procedure push(var s:stack;x:char); begin if top=100 then writeln(overflow) else begin top:=top+1; stop:=x; end; end;,20,begin主程序 while not eof do begin setnull(s); while not e

11、oln do begin read(ch); case ch of #:pop(s); :setnull(s) else push(s,ch) end; end; for i:=1 to top do write(si); writeln; readln; end ; end.,eof函數(shù)，判斷文件是否結(jié)束,eoln函數(shù)，判斷一行是否結(jié)束,出棧,置棧為空,入棧,輸出,21,例4.2后綴表達(dá)式計(jì)算,【問(wèn)題分析】 為了便于用程序計(jì)算將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式: 35+（6-8/4)7中綴表達(dá)式 3 56 8 4 / -7+后綴表達(dá)式 如何計(jì)算后綴表達(dá)式的值,22,請(qǐng)你試一試,將下列中綴表達(dá)式轉(zhuǎn)換

12、成后綴表達(dá)式：,16-9*（4+3） 2*(x+y)/(1-x) (25+8)*(4*(4+7)+7),16943+*-,2xy+*1x-/,258+447+*7+*,23,# -1,6,- 1,9,* 2,( 0,4,+ 1,3,+,*,-,5,+,+ 1,6 9 4 3 +*-5 +,6-9*(4+3)+5#,#,輸出隊(duì)列,24,例4.3表達(dá)式計(jì)算后綴表達(dá)式計(jì)算,【數(shù)據(jù)結(jié)構(gòu)】 const n=20; type arr=array 1.n of char; arr1=array 1.n of real; var a:arr; s:arr1; i,j,k,top:integer; t,x:re

13、al; ch:char;,存儲(chǔ)后綴表達(dá)式,棧,25,procedure readdata(var a:arr); var i,k:integer; begin assign(input,count.in);reset(input); read(ch);i:=0; while ch# do begin i:=i+1;ai:=ch; read(ch); end; i:=i+1; ai:=#;close(input); end;,讀入后綴表達(dá)式,26,function comp(a:arr; var s:arr1):real; var i,k:integer; begin i:=1; top:=0;

14、 ch:=ai; while ch# do begin case ch of 0.9:begin x:=0; while (ch ) do begin x:=x*10+ord(ch)-ord(0); i:=i+1; ch:=ai; end; top:=top+1; end;,將數(shù)字字符串轉(zhuǎn)換為實(shí)數(shù),27,+:begin x:=stop-1+stop;dec(top); end; -:begin x:=stop-1-stop; dec(top); end; *:begin x:=stop-1*stop; dec(top); end; /:begin if stop0 then begin x:=

15、stop-1/stop;dec(top); end else begin writeln(error); close(output); halt; end; end; end ; case stop:=x;i:=i+1;ch:=ai; end ;while comp:=trunc(stop*1000+0.5)/1000; end;function,28,begin assign(output,count.out); rewrite(output); for i:=1 to n do si:=0; readdata(a); t:=comp(a,s); writeln(t=,t:0:2); clo

16、se(output); end.,主程序,29,隊(duì)列的基礎(chǔ)知識(shí),到醫(yī)院看病排隊(duì)掛號(hào)排隊(duì) 在學(xué)校食堂就餐排隊(duì)買(mǎi)飯 到銀行辦理存款或取款業(yè)務(wù)排隊(duì) 共同的特征 嚴(yán)格遵守先來(lái)后到原則 不存在插隊(duì)現(xiàn)象,A3 A4 A5 A6 A7 A8,A1,A2,A10,A9,隊(duì)列,30,1.1 隊(duì)列的概念,隊(duì)列是限定在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。 隊(duì)尾(rear)：可以插入的一端 隊(duì)首(front)：可以刪除的一端,A1 A2A3 A4 Ai,“先進(jìn)先出”（FIFOfirst in first out）線性表。,31,1.2 隊(duì)列的基本術(shù)語(yǔ),隊(duì)首指針f：指向隊(duì)首元素 初始狀態(tài)：f=0 隊(duì)尾指針r

17、：指向隊(duì)尾元素 初始狀態(tài)：r=0 出隊(duì)：從隊(duì)列頭部刪除一個(gè)元素 進(jìn)隊(duì)：將一個(gè)元素插入隊(duì)列尾部,32,1.3 隊(duì)列的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ),Const m=隊(duì)列元素的上限； Type queue=array1.m of elemtype； 隊(duì)列的類型定義 Var q：queue； 隊(duì)列 f, r: integer ; 隊(duì)尾指針和隊(duì)首指針,33,2隊(duì)列的基本操作運(yùn)算,（1）初始化隊(duì)列 Qini (Q) （2）判斷隊(duì)列是否為空 qempty(Q) （3）判斷隊(duì)列是否為滿qfull(Q) （4）入隊(duì) QADD(Q,X) （5）出隊(duì) QDel(Q,X),34,2.1初始化操作過(guò)程,設(shè)定隊(duì)列為空,procedu

18、re Qini (var Q:queue); begin f:=0; r:=0; end;,f=r=0,35,2.2 判斷隊(duì)列是否為空的函數(shù),若隊(duì)列Q為空，則返回值true，否則返回值false。,function qempty(Q:queue):Boolean; begin qempty:=(r=f) end;,36,2.3 判斷隊(duì)列是否為滿的函數(shù),若隊(duì)列滿，則返回值true，否則返回值false。,function qfull(Q:queue):Boolean; begin Qfull:=（rm); end;,37,2.4元素進(jìn)隊(duì)過(guò)程,若隊(duì)列Q不滿時(shí)，把元素X插入到隊(duì)列Q的隊(duì)尾，否則返回信

19、息“Overflow”。,procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) 上溢 then writeln (overflow) else begin r:=r+1； qr:=x； end； end；,將元素插入隊(duì)尾,38,2.5 元素出隊(duì)過(guò)程,若隊(duì)列Q不空，則把隊(duì)頭元素刪除并返回值給X，否則輸出信息“Underflow”。,procedure Qdel(var q:queue;var x:elemtype); begin if qempty(Q) 下溢 then writeln(Underflow) else begin f:

20、=f+1; x:=qf; end； end;,從隊(duì)首刪除一個(gè)元素,39,例題4.4 周末舞會(huì),假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。規(guī)定每個(gè)舞曲能有一對(duì)跳舞者。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲?，F(xiàn)要求寫(xiě)一個(gè)程序，模擬上述舞伴配對(duì)問(wèn)題。,40,例題4.4 周末舞會(huì),輸入3個(gè)整數(shù)m，n，k，分別表示男士人數(shù)、女士人數(shù)、幾輪舞曲。 例如：24 6 輸出各輪舞曲的配對(duì)方案。 例如：,1 2 3 4 1 22,41,例題4.4 周末舞會(huì),設(shè)計(jì)兩個(gè)隊(duì)列分別存放男士和女士。每對(duì)跳舞的人一旦跳完后就回到隊(duì)尾等

21、待下次被選。 m=3 n=2 k=6,A,B,1,2,3,1,2,42,例題4.4 周末舞會(huì),const max=1000; var a,b:array1.max of integer; m,n,k,i,f1,r1,f2,r2:integer;,數(shù)據(jù)結(jié)構(gòu) a、b分別為兩個(gè)隊(duì)列 f1,r1,f2,r2分別為兩個(gè)隊(duì)列的首尾指針,43,例題4.4 周末舞會(huì),readln(m，n，k); for i:=1 to m do ai:=i; for i:=1 to n do bi:=i; f1:=0;r1:=m; f2:=0;r2:=n;,初始化 讀入數(shù)據(jù) 建立兩個(gè)初始隊(duì)列,44,例題4.4 周末舞會(huì),模擬

22、舞會(huì) 配對(duì),for i:=1 to k do begin f1:=f1+1; f2:=f2+1; writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; r2:=r2+1;br2:=bf2; end；,45,const max=10000; var a,b:array1.max of integer; m,n,k,i,f1,r1,f2,r2:integer; begin readln(m，n，k); for i:=1 to m do ai:=i; for i:=1 to n do bi:=i; f1:=0;r1:=m;f2:=0;r2:=n; for i:=1 t

23、o k do begin f1:=f1+1; f2:=f2+1; writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; r2:=r2+1;br2:=bf2; end； end.,46,2.6隊(duì)列的“假溢出”現(xiàn)象,當(dāng)尾指針指向數(shù)組的最后一個(gè)元素時(shí)，即r=m，下一個(gè)元素就不能進(jìn)隊(duì)了。但是數(shù)組的前部因元素出隊(duì)空出很多位置閑置無(wú)用，這種現(xiàn)象稱為“假溢出”。 將m+1的元素放入1，指針繞數(shù)組移動(dòng)。,r:=r+1 if rm then r:=r mod m,r:=(r mod m)+1,47,2.7 循環(huán)隊(duì)列,初始化：f=r=0 隊(duì)空：f=r 隊(duì)滿：f=(r+1) mod

24、m 進(jìn)隊(duì)：r=(r+1) mod m 出隊(duì)：f=(f+1) mod m 元素個(gè)數(shù)：(r-f+m) mod m,48,圓盤(pán)找數(shù)，如圖所示：找出4個(gè)相鄰的數(shù)，使其相加之和最大和最小的是哪4個(gè)數(shù),給出它們的起始位置。,s=ai+a(i+1)mod 20+a(i+2)mod 20) +a(i+3)mod 20),49,給你一個(gè)長(zhǎng)度為N的數(shù)組，一個(gè)長(zhǎng)為K的滑動(dòng)的窗體從最左移至最右端，你只能見(jiàn)到窗口的K個(gè)數(shù)，每次窗體向右移動(dòng)一位，你的任務(wù)是找出窗口在各位置時(shí)的最小數(shù),50,輸入格式： 第1行n,k,第2行為長(zhǎng)度為n的數(shù)組 輸出格式： 1行，每個(gè)位置的最小數(shù) 樣例： window.in 8 3 1 3 -1

25、 -3 5 3 6 7 window.out -1 -3 -3 -3 3 3 數(shù)據(jù)范圍： 20%： n=500; 50%: n=100000; 100%: n=1000000;,51,例題4.5 迷宮問(wèn)題,編一個(gè)程序，找出一條通過(guò)迷宮的路徑。這里有蘭色方塊的區(qū)域表示走不通，將一只老鼠從入口處經(jīng)過(guò)迷宮到出口處的最短的一條通路打印出來(lái)。,52,例題4.5 迷宮問(wèn)題,【問(wèn)題分析】 （1）用二維數(shù)組表示迷宮，1代表不能走入的區(qū)域，0表示可以走通。,53,例題4.5 迷宮問(wèn)題,（2）老鼠在迷宮中怎樣探索路徑？有幾個(gè)方向可以探索呢？,（a）有三個(gè)方向可以試探。 （b）有五個(gè)方向可以試探。 （c）有八個(gè)方向

26、可以試探。,a,b,c,54,例題4.5 迷宮問(wèn)題,55,（x,y）,0 1,1 1,1 0,1 -1,0 -1,-1 -1,-1 0,-1 1,56,例題4.5 迷宮問(wèn)題,（3）用一個(gè)隊(duì)列記錄探索的路徑。 x：當(dāng)前位置的所在行 y：當(dāng)前位置的所在列 pre：前一個(gè)位置的記錄在隊(duì)列中的序號(hào),57,隊(duì)列操作的一般過(guò)程 （1）初始化： 指針賦初值，f:=0;r:=1; 第一個(gè)結(jié)點(diǎn)進(jìn)隊(duì)，q1.1:=1;q2.1:=1;q3,1:=0; （2）出隊(duì)操作，f:=f+1; x:=q1,f;y:=q2,f; （3）依次探索八個(gè)方向，如果能走通，則進(jìn)隊(duì)， r:=r+1; q1.r:=x;q2.r:=y;q3,

27、r:=f; （4）重復(fù)(2)(3)步，直到目標(biāo)狀態(tài)出現(xiàn)，輸出結(jié)果，結(jié)束。 （5）如果目標(biāo)狀態(tài)一直不出現(xiàn)，則隊(duì)空循環(huán)結(jié)束，無(wú)解。,58,例題4.5 迷宮問(wèn)題,【數(shù)據(jù)結(jié)構(gòu)】 const dx=array1.8 of integer=(0,1,1,1,0,-1,-1,-1); dy=array1.8 of integer=(1,1,0,-1,-1,-1,0,1); max=10; type sqtype=array1.3,1.max*max of integer; var mg:array0.max+1;0.max+1 of integer; sq:sqtype; f,r,i,j,n,m:integ

28、er;,59,Procedure mglj(var sq:sqtype); Begin f:=0;r:=1;sq1,1:=1;sq2,1:=1;sq3,1:=0; While fr do Begin f:=f+1; x:=sq1,f;y:=sq2,f; for v:=1 to 8 do begin i:=x+dxv; j:=y+dyv; if mgi,j=0 then begin inc(r);sq1,r:=i;sq2,r:=j;sq3,r:=f; mgi,j:=-1; end; if (i=m) and (j=n) then print; end; for End; Writeln(迷宮無(wú)路

29、徑); End;,60,Procedure print(var sq:sqtype；r:integer); Begin i:=r; repeat writeln(,sq1,i,sq2,i,); i:=sq3,i until i=0； halt； End;,(6,8) (5,7) (4,6) (4,5) (3,4) (3,3) (2,2) (1,1),61,例題4.6 分油問(wèn)題,【問(wèn)題描述】 在10升的容器中裝有10升油，另有兩個(gè)7升和3升的空容器，現(xiàn)要求用這三個(gè)容器倒油，使得最后在10升和7升的容器中各有5升油。,C10 C7 C3 10 0 0 3 7 0 3 4 3 6 4 0 6 1 3

30、 9 1 0 9 0 1 2 7 1 2 5 3 5 5 0,62,例題4.6 分油問(wèn)題,【問(wèn)題分析】 三個(gè)容器可以看作三個(gè)變量 C10，C7，C3，每次倒油的可能性只有如下六種情況： C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油,63,（1）(c100) and (c77),（2）(c100) and (c33),（3）c70,c7c10: c10:=c10+c7;c7:=0;,（4）(c70) and (c33),64,例題4.6 分油問(wèn)題,【數(shù)據(jù)結(jié)構(gòu)】 Var q:array 1.4,1.100

31、 of integer; f,r,p:integer; c10,c7,c3:integer;,65,begin f:=0;r:=1; q1,1:=10;q2,1:=0;q3,1:=0; q4,1:=0; While fr do Begin inc(f); c10:=q1,f;c7:=q2,f; c3:=q3,f; for p:=1 to 6 do begin case p of 1:f1(c10,c7,c3); 2:f2(c10,c7,c3); 3:f3(c10,c7,c3); 4:f4(c10,c7,c3); 5:f5(c10,c7,c3); 6:f6(c10,c7,c3); End; en

32、d;,主程序,if fr then writeln(no answer); end.,66,procedure f1(w10,w7,w3:integer); begin if (w100) and (w77 then begin w10:=w10+w7-7;w7:=7;end else begin w7:=w10+w7;w10:=0;end; if flag(w10,w7,w3) then begin inc(r); q1,r:=w10;q2,r:=w7; q3,r:=w3;q4,r:=f; end; if (w10=5) and (w7=5) then print; end;,67,func

33、tion flag(w10,w7,w3):boolean; var i:integer; begin flag:=true; for i:=1 to r do if (q1,i=w10) and (q2.i=w7) and (q3.i=w3) then flag:=false; end;,68,上機(jī)練習(xí)1,begin for i:=1 to 100 do si:=0; top:=0; repeat read(x); if x0 then begin top:=top+1; stop:=x; end; until x=0; while top0 do begin write(stop:4); t

34、op:=top-1; end; readln; end.,1. 讀入若干個(gè)整數(shù)，把它們逐個(gè)地壓棧，讀入1個(gè)0表示結(jié)束（0不要壓棧），再逐個(gè)出棧。,program zh1; var s:array1.100of integer; top,x,i:integer;,69,上機(jī)練習(xí),2.進(jìn)制轉(zhuǎn)換work1 輸入n進(jìn)制的數(shù)m與要轉(zhuǎn)換成的數(shù)的進(jìn)制p 。 如：輸入一個(gè)數(shù)m : ABC.CBA 輸入此數(shù)的進(jìn)制n : 16 輸入要轉(zhuǎn)換成的數(shù)的進(jìn)制p : 2 輸出： ABC.ABC(16)=101010111100.11001011101(2) 【輸入】 輸入僅三行，第一行為n進(jìn)制的數(shù)m，第二行為m的進(jìn)制n，第

35、三行是要轉(zhuǎn)換成的數(shù)的進(jìn)制p。（小數(shù)部分精度要求5位小數(shù)） 【輸出】 n進(jìn)制的數(shù)m的p進(jìn)制結(jié)果。 【樣例】 輸入（work1.in） ABC.CBA 16 2 輸出（work1.out） ABC.ABC(16)=101010111100.11001011101(2),70,3.括弧匹配檢驗(yàn)work2 假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（）或（ （ ）或 （）均為錯(cuò)誤的匹配。 現(xiàn)在的問(wèn)題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？ 輸入一個(gè)只包含圓括號(hào)和方括號(hào)的字符串，判斷字符串中的括號(hào)是否匹配，匹配就輸出 “OK” ，不匹配就輸出“Wrong”。 輸入一個(gè)字符串： （） 輸出： OK 【輸入】 輸入僅一行字符（字符個(gè)數(shù)小于255） 【輸出】 匹配就輸出 “OK” ，不匹配就輸出“Wrong”。 【樣例】 輸入（work2.in） （） 輸出（work2.out） Wrong,71,上機(jī)練習(xí)4 家庭