1、第三章3.5假設(shè)s和x用于表示堆棧進(jìn)入和堆棧退出操作，初始狀態(tài)和最終狀態(tài)為空的堆棧進(jìn)入和堆棧退出操作序列可以表示為僅由s和x組成的序列?？刹僮鞯男蛄蟹Q為合法序列(例如，SXXSX是合法序列，SXS是非法序列)。本文試圖給出一個通用的標(biāo)準(zhǔn)來區(qū)分給定序列與合法序列或非法序列，并證明兩個不同的合法(堆棧操作)序列(對于相同的輸入序列)不可能得到相同的輸出元素(注意：在這種情況下，它指的是元素實(shí)體，而不是值)序列。解決方案：一般規(guī)則：任何前n個序列中的s的數(shù)目必須大于或等于x的數(shù)目，并且整個序列中的s的數(shù)目必須等于x的數(shù)目。證據(jù)：讓兩個法律序列：T1=SXST2=SXX假設(shè)前n個操作是相同的，并且從第

2、n個操作開始，它是具有不同序列的開始操作點(diǎn)。由于前n個操作是相同的，此時(shí)兩個堆棧(堆棧A和堆棧B)的存儲條件完全相同，假設(shè)堆棧的頂部元素此時(shí)都是A。第n個1操作是不同的，所以T1的第n個1操作是s，T2的第n個1操作是x。假設(shè)B是堆疊的，T1的輸出順序必須是先B后A；T2將是一個堆棧，它的輸出順序必須是先a后B.由于T1的輸出是ba而T2的輸出序列是ab這表明兩個不同的合法堆棧操作序列的輸出元素序列一定是不同的。3.9嘗試將下面的遞歸過程重寫為遞歸過程。void ditui(int n)int I；i=n。而(i1)coutxif(x=0)sum=0；其他測試(總和)；sum=x；標(biāo)準(zhǔn)輸出#包

3、括#定義STACK_INIT_SIZE 100#定義TURE 1#定義FALSE 0#定義ok 1#定義錯誤0#定義不可行-1typedef int selemtypetypedef int狀態(tài)；typedef結(jié)構(gòu)int * base2；selem type * top2；int stacksizesqstack。狀態(tài)INITstack(sqstack * s)int * p；p=(selem type *)malloc(STACK _ INIT _ SIZE * sizeof(selem type)；(*s)?；鶖?shù)0=(*s)。top0=p；(*s)?；鶖?shù)1=(*s)。top1=p STAC

4、K _ INIT _ SIZE-1；如果(！(*s)?；?)出口(-2)；如果(！(*s)。基地1)出口(-2)；返回ok；狀態(tài)推送(sqstack * s，int i，selemtype e)if(i=0)if(*)頂部0=(*)基本0 (STACK_INIT_SIZE/2)-1)返回錯誤；else *(s)。top0=e；返回ok；if(i=1)if(*)頂部1=(*)base1-(STACK_INIT_SIZE/2) 1)返回錯誤；else *(s)。top1-=e；返回ok；返回錯誤；狀態(tài)彈出(sqstack * s，int i，selemtype * e)if(i=0(*s)。前0

5、=(* s)。base0返回錯誤；if(i=1(*s)。頂部1=(*)。base1)返回錯誤；if(i=0) * e=*(-(*)s)。top0)；返回ok；if(i=1) * e=*(-(*)s)。top1)；返回ok；void main()sqstack sta。selem type e；selem type * p；int I；如果(INITstack(sta) printf(“已創(chuàng)建雙堆棧 n”)；Printf(請輸入推送結(jié)束(0/1)和推送元素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆疊)；Printf(請輸入推送結(jié)束(0/1)和推送元

6、素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆疊)；Printf(請輸入推送結(jié)束(0/1)和推送元素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆疊)；Printf(左堆棧元素：)；p=sta . base0；同時(shí)(sta.top0！=p)printf(“% d”，* p)；p；Printf(右堆棧元素：)；p=sta . base1；同時(shí)(sta.top1！=p)printf(“% d”，* p)；p-；printf( n請輸入堆棧結(jié)尾(0/1): n )；scanf(“% d”，I)；如果(Pop(s

7、ta，即e) printf(n堆棧頂部元素%d從堆棧中出來n ，e)；Printf(左堆棧元素：)；p=sta . base0；同時(shí)(sta.top0！=p)printf(“% d”，* p)；p；Printf(右堆棧元素：)；p=sta . base1；同時(shí)(sta.top1！=p)printf(“% d”，* p)；p-；運(yùn)行結(jié)果：3.21假設(shè)表達(dá)式由單字母變量和雙目四個運(yùn)算符組成。試著寫一個算法，將正常書寫和正確書寫的表達(dá)式轉(zhuǎn)換成相反的波蘭表達(dá)式。解決方案：程序源代碼：#包括#包括#定義尺寸100typedef char selemtypetypedef結(jié)構(gòu)selemtype * bas

8、eselemtype * topint大??；堆棧；int優(yōu)先(char c1，char c2)char ch5= #-*/；int i=0，j=0；如果(c1=()返回0；當(dāng)(chi chi!=c1) i。如果(I=2)I-；/加和減可認(rèn)為是同級別的運(yùn)算符如果(I=4)I-；/乘和除可認(rèn)為是同級別的運(yùn)算符當(dāng)chj chj！(C2)j；if(j=2)j-；if(j=4)j-；如果(ij)返回1；否則返回0；void main()堆棧無線電臺臨時(shí)使用許可證ch=0，CT；斯塔。base=(selem類型*)malloc(SIZE * SIZeof(selem類型)；如果(！sta.base)出口(

9、0)；斯塔。top=sta?；?；斯塔。大小=0；* sta。top=#；printf(請輸入表達(dá)式： n )；同時(shí)(ch！=#*sta.base=#)ch=getchar()；如果(a=chch=z)printf(% c ，ch)；其他if(ch=#)CT=*(-sta。頂部)；同時(shí)(ct！=#)印刷字體( % c ，印刷字體)；CT=*(-sta。頂部)；-斯塔。頂部；其他if(ch=()* sta。top=ch其他if(ch=)CT=*(-sta。頂部)；同時(shí)(ct！=()印刷字體( % c ，印刷字體)；CT=*(-sta。頂部)；否則CT=*(sta。top-1)；如果(先驗(yàn)(ct，

10、ch)=0)* sta。top=ch否則CT=*(-sta。頂部)；同時(shí)（優(yōu)先(ct，ch)印刷字體( % c ，印刷字體)；CT=*(-sta。頂部)；*(sta.top)=ch .sta.top運(yùn)行結(jié)果：3.22如題3.21的假設(shè)條件，試寫一個算法，對以逆波蘭式表示的表達(dá)式求值。解：程序源代碼：#包括#包括#定義最大大小堆棧100#定義增量10#定義ok 1#定義錯誤-100typedef int elemtype2typedef int狀態(tài)；typedef結(jié)構(gòu)elemtype2 * topelemtype2 * baseint大?。?stack2狀態(tài)initstack2(stack2 da)爸爸。base=(elem類型2 *)malloc(max _