树与二叉树1_习题与解答.doc

1、括号的匹配（表达式的合法性检查）问题描述假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。问题分析假设输入的字符串存储在c中（varc:string255）。我们可以定义一个栈：vars:array1.maxnofchar;top:integer;用它来存放表达式中从左往右的左圆括号（maxn=20）。算法的思路为：顺序（从左往右）扫描表达式的每个字符ci，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。参考程序programlx5;constmaxn=20;varc:string;functionjudge(c:string):boolean;vars:array1.maxnofchar;top,i:integer;ch:char;beginjudge:=true;top:=0;i:=1;ch:=ci;whilechdobeginif(ch=()or(ch=)thencasechof(:begintop:=top+1;stop:=(end;):iftop0thentop:=top-1elsebeginjudge:=false;exitend;end;i:=i+1;ch:=ci;end;iftop0thenjudge:=false;end;beginmainassign(input,match.in);assign(output,match.out);reset(input);rewrite(output);readln(c);ifjudge(c)thenwriteln(YES)elsewriteln(NO);close(input);close(output);end.2、编程把中缀表达式转换成后缀表达式问题描述输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序一致。为简单起见，假设输入的中缀表达式由（加）、（减）、*（乘）、（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即括号内部至少有一个运算符号。以下是一个运行实例233。样例输入X+A*（Y-B）-Z/F样例输出XAYB-*+ZF/-算法设计设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾相应地加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级；此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。上图是对范例表达式的扫描示意图。这样，我们需要事先把所有运算符号的优先级定义并存放好，这很简单，以下程序中的数组f就是用来存放运算符之间的优先级关系的。1()表示前面的运算符优先于后面的运算符，-1(-*/(ERROR#ERROR=参考程序programlx6(input,output);constmax=100;op_set:setofchar=+,-,*,/;letter:setofchar=A.Z;varexpression,result:string;procedurescan(expression:string);vari,top1,top2:integer;ovs:array1.maxofstringmax;ops:array1.maxofchar;f:array#./,#./ofshortint;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-,):=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(,-:=-1;f(,*:=-1;f(,/:=-1;f(,(:=-1;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:=1tolength(expression)do逐个扫描beginifexpressioniinletter是字母就进栈thenbegintop1:=top1+1;ovstop1:=expressioniendelsebegin运算符whilefopstop2,expressioni=1do栈顶运算符优先级高于当前运算符begin取栈顶上面的两个元素运算后，再压栈ovstop1-1:=ovstop1-1+ovstop1+opstop2;top1:=top1-1;top2:=top2-1end;iffopstop2,expressioni=0thentop2:=top2-1优先级相同，则抵消elsebegintop2:=top2+1;栈顶运算符优先级低于当前运算符，则压栈opstop2:=expressioniend;endend;result:=ovs1返回结果end;beginmainwrite(Inputaexpression:);readln(expression);scan(expression);writeln(Theresultis:,result)end.3、编程求一个后缀表达式的值问题描述从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以作为结束标志。问题分析后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。比如，169*(4+3)转换成后缀表达式为：16943+*，在字符数组A中的形式为：栈中的变化情况：运行结果：-47参考程序1programlx7_1;constmaxn=20;varstack:array1.maxnofinteger;s:string;functioncomp(s:string):integer;varch:char;i,top,x,y,z:integer;begintop:=0;i:=1;ch:=si;whilei=length(s)dobegincasechof0.9:beginx:=0;whilechdobeginx:=x*10+ord(ch)-ord(0);i:=i+1;ch:=si;end;top:=top+1;stacktop:=x;end;+:beginx:=stacktop;top:=top-1;y:=stacktop;z:=y+x;stacktop:=zend;-:beginx:=stacktop;top:=top-1;y:=stacktop;z:=y-x;stacktop:=zend;*:beginx:=stacktop;top:=top-1;y:=stacktop;z:=y*x;stacktop:=zend;/:beginx:=stacktop;top:=top-1;y:=stacktop;z:=ydivx;stacktop:=zend;end;i:=i+1;ch:=si;end;whilecomp:=stacktop;end;beginmainwriteln(inputastring(_over):);readln(s);writeln(result=,comp(s);readln;end.参考程序2programlx7_2;typestack=recorddata：array1.100ofreal；存放实型数top：0.100；end；vars：stack；ch：char；i：integer；x:real;a:array1.30ofchar;functionpop(vars：stack):real；出栈beginpop:=s.datas.top;s.top:=s.top-1；end；procedurepush(vars：stack；x：real);入栈begins.top:=s.top+1；s.datas.top:=xend；begin主程序i:=0;repeati:=i+1;read(ai);将表达式存入数组auntilai=;s.top:=0;清空栈i:=1;i为a数组的下标ch:=ai;whilechdobegincasechof0.9:begin产生完整的数x:=0;whilechdobeginx:=x*10+ord(ch)-ord(0);i:=i+1;ch:=ai;end;end;+:x:=pop(s)+pop(s)-:beginx:=pop(s);x:=pop(s)-x;end;*:x:=pop(s)*pop(s);/:beginx:=pop(s);x:=pop(s)/x;end;end;push(s,x);将上面得到的x入栈i:=i+1;ch:=ai;继续扫描a数组end;writeln(pop(s)end.4、计算后缀表达式的值编一个程序，输入一个实数中缀表达式（由0-9组成的运算数、加（+）、减（-）、乘（*）、除（/）四种运算符、左右小括号、小数点组成。注意“-”也可作为负数的标志），判断表达式是否合法，如果不合法，请输出“NO”；否则求出后缀表达式的值并输出。注意：必须用栈操作，不能直接输出表达式的值；8*-5是不合法的，必须写成8*（-5）；12.和.5也算合法，分别表示12.0和0.5；参考程序programlx8;constmax=100;list_1:setofchar=*,/,+,-,.,(,),0.9;list_2:setofchar=*,/,+,-;number:setofchar=0.9;zero=0.0000000001;varsin,tmp:string;result:real;procedureouterror;beginwriteln(No);halt;end;functionerror(s:string):boolean;vari,j,k:longint;f:boolean;beginf:=false;k:=0;fori:=1tolength(s)dobeginifnot(siinlist_1)thenf:=true;if(siinlist_2)and(si-1inlist_2)thenf:=true;if(si=()and(si-1=)thenf:=true;ifsi=(theninc(k);ifsi=)thendec(k);end;ifk0thenf:=true;error:=f;end;proceduredealwithnegative(vars:string);vari,j,k:longint;tmp:string;begintmp:=;i:=1;fori:=1tolength(s)dobeginif(si=-)and(i=1)or(si-1=()thentmp:=tmp+0;tmp:=tmp+si;end;s:=tmp;end;functionconvert(s:string;vari:longint):real;varr:real;tmp:string;p:longint;begintmp:=;while(siinnumber)or(si=.)dobegintmp:=tmp+si;inc(i);end;i:=i-1;val(tmp,r,p);ifp0thenouterror;convert:=r;end;functioncalc(r1,r2:real;ch:char):real;begincasechof+:calc:=r1+r2;-:calc:=r1-r2;*:calc:=r1*r2;/:beginifabs(r2)zerothenbeginwriteln(dividedbyzero);halt;end;calc:=r1/r2;end;end;end;procedurescan(sin:string;varresult:real);vari,j,top1,top2:longint;ovs:array1.maxofreal;ops:array1.maxofchar;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*,+:=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;iferror(sin)thenouterror;dealwithnegative(sin);sin:=sin+);ops1:=(;top1:=0;top2:=1;i:=1;whilei=length(sin)dobeginif(siniinnumber)or(sini=.)thenbegintop1:=top1+1;ovstop1:=convert(sin,i);endelsebeginwhilefopstop2,sini=1dobeginovstop1-1:=calc(ovstop1-1,ovstop1,opstop2);top1:=top1-1;top2:=top2-1;end;iffopstop2,sini=0thentop2:=top2-1elsebegintop2:=top2+1;opstop2:=sini;end;end;inc(i);end;result:=ovs1;end;beginmainwrite(Inputaexpression:);readln(sin);scan(sin,result);writeln(Theresultis:,result:0:3);end.5、单词查找树问题描述 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：1根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；2从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；3在满足上述条件下，该单词查找树的结点数最少。4例如图6_2左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。问题输入 输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。问题输出 输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。 样例输入 AANASPASASCASCIIBASBASIC 样例输出 13 算法分析首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加入单词查找树中去。但，本问题只是问你结点总数，而非建树方案，且有32K文件，所以应该考虑能不能通过不建树就直接算出结点数？为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则说单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中已有单词的差的最小值。单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是，得出建树的等效算法： 读入文件； 对单词列表进行字典顺序排序； 依次计算每个单词对前一单词的差，并把差累加起来。注意：第一个单词相对于“空”的差为该单词的长度； 累加和再加上1（根结点），输出结果。就给定的样例，按照这个算法求结点数的过程如下表：表6_1原单词列表排序后的列表差值总计输出AA11213ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2数据结构 先确定32K（32*1024=32768字节）的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复，所以长度为1的单词（单个字母）最多26个；长度为2的单词最多为26*26=676个；因为每个单词后都要一个换行符（换行符在计算机中占2个字节），所以总共已经占用的空间为：（1+2）*26+（2+2）*676=2782字节；剩余字节（32768-2782=29986字节）分配给长度为3的单词（长度为3的单词最多有 26*26*26=17576个）有29986/（3+2）5997。所以单词数量最多为26+676+5997=6699。定义一个数组：a：array1.32767 of char；把所有单词连续存放起来，文件中每个单词后的换行符转换成数组中的一个“空格”字符。这样既省略了一个存放单词长度的数组，又方便且节省了一点空间。另外为了排序，再设一个数组index:array1. 6700 of integer；存放每个单词在a中的起始位置。这样，排序时用a比较，但只要交换index的值就可以了。参考程序Program p6_1(Input, Output)；Var 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开始的字符串和从aj开始的字符串Begin 大小，小于则返回False，否则返回True W