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

1、括号的匹配（表达式的合法性检查）
[问题描述]
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。
[问题分析]
假设输入的字符串存储在c中（var c:string[255]）。
我们可以定义一个栈：var s:array[1..maxn] of char;
top:integer;
    用它来存放表达式中从左往右的左圆括号（maxn=20）。
    算法的思路为：顺序（从左往右）扫描表达式的每个字符c[i]，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。
[参考程序]
program lx5;
  const maxn=20;
  var c:string;
  function judge(c:string):boolean;
  var s:array[1..maxn] of char;
      top,i:integer;
      ch:char;
  begin
    judge:=true;
    top:=0;
    i:=1;ch:=c[i];
    while ch<>'@' do
      begin
        if (ch='(') or (ch=')') then
          case ch of
              '(' :  begin top:=top+1;s[top]:='(' end;
              ')' :  if top>0 then top:=top-1
                              else begin judge:=false;exit end;
          end;
        i:=i+1;ch:=c[i];
      end;
    if top<>0 then  judge:=false;
  end;
begin   {main}
  assign(input,'match.in');
  assign(output,'match.out');
  reset(input);
  rewrite(output);
  readln(c);
  if judge(c) then  writeln('YES')  else writeln('NO');
  close(input);
  close(output);
end.

2、编程把中缀表达式转换成后缀表达式
[问题描述]
输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、*（乘）、／（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即括号内部至少有一个运算符号。以下是一个运行实例233。
[样例输入]
 X+A*（Y-B）-Z/F
[样例输出]
 XAYB-*+ZF/-
[算法设计]
设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾相应地加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级；此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。
上图是对范例表达式的扫描示意图。
这样，我们需要事先把所有运算符号的优先级定义并存放好，这很简单，以下程序中的数组f就是用来存放运算符之间的优先级关系的。1(>)表示前面的运算符优先于后面的运算符，-1(<)表示后面的运算符优先于前面的运算符，0(=)表示前面的运算符的优先级与后面的运算符相同，2(ERROR)表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。
需要补充的是：左括号的优先级是最高的，而里层的左括号比外层的左括号更优先，右括号的优先级是除#号以外最低的，但左括号和右括号的优先级则是相等的，这样定义的目的是为了消去括号。
以上规律列表如下：
 + - * / （ ） #
+ > > < < < > >
- > > < < < > >
* > > > > < > >
/ > > > > < > >
( < < < < < = ERROR
) > > > > ERROR > >
# < < < < < ERROR =
[参考程序]
program lx6(input,output);
const max=100;
      op_set:set of char=['+','-','*','/'];
      letter:set of char=['A'..'Z'];
var expression,result:string;
procedure scan(expression:string);
var i,top1,top2:integer;
    ovs:array [1..max] of string[max];
    ops:array [1..max] of char;
    f:array['#'..'/','#'..'/'] of shortint;
begin
   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['(','(']:=-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+'#';
  ops[1]:='#'; 
top1:=0;
top2:=1;
  for i:=1 to length(expression) do   {逐个扫描}
    begin
      if expression[i] in letter    {是字母就进栈}
       then begin top1:=top1+1; 
ovs[top1]:=expression[i] 
end
       else begin      {运算符}
              while f[ops[top2],expression[i]]=1 do {栈顶运算符优先级高于当前运算符}
                begin  {取栈顶上面的两个元素运算后，再压栈}
                  ovs[top1-1]:=ovs[top1-1]+ovs[top1]+ops[top2];
                  top1:=top1-1;
                  top2:=top2-1
                end;
              if f[ops[top2],expression[i]]=0
                 then top2:=top2-1              {优先级相同，则抵消}
                 else begin top2:=top2+1;{栈顶运算符优先级低于当前运算符，则压栈}
ops[top2]:=expression[i] 
end;
           end
    end;
    result:=ovs[1]  {返回结果}
end;
begin{main}
     write('Input a expression:');
     readln(expression);
     scan(expression);
     writeln('The result is: ',result)
end.
3、编程求一个后缀表达式的值
[问题描述]
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。
[问题分析]
后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。
比如，16–9*(4+3)转换成后缀表达式为：16□9□4□3□+*–，在字符数组A中的形式为：

栈中的变化情况：
运行结果：-47
[参考程序1]
program lx7_1;
const maxn=20;
var stack:array[1..maxn] of integer;
    s:string;
function comp(s:string):integer;
  var ch:char;
      i,top,x,y,z:integer;
  begin
    top:=0;
    i:=1;
    ch:=s[i];
    while i<=length(s) 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:=s[i];
                                     end;
                   top:=top+1;
                   stack[top]:=x;
                 end;
             '+':begin x:=stack[top];top:=top-1;y:=stack[top];z:=y+x;stack[top]:=z
end;
'-' :begin
  x:=stack[top];top:=top-1;y:=stack[top];z:=y-x;stack[top]:=z
end;
'*' :begin
       x:=stack[top];top:=top-1;y:=stack[top];z:=y*x;stack[top]:=z
     end;
'/' :begin
x:=stack[top];top:=top-1;y:=stack[top];
z:=y div x;stack[top]:=z
end;
      end;
      i:=i+1;
      ch:=s[i];
    end;{while}
    comp:=stack[top];
  end;
begin{main}
  writeln('input a string(@_over):');
  readln(s);
  writeln('result= ',comp(s));
  readln;
end.
[参考程序2]
program lx7_2;
type  stack=record
              data：array[1 . . 100] of  real；{存放实型数}
              top：0 . . 100；
     end；
var
   s：stack；ch：char；i：integer；x:real;
   a:array[1..30] of char;
function  pop(var s：stack): real；｛出栈｝
begin
   pop:=s.data[s.top];
   s.top:=s.top -1；
end；
procedure push(var s：stack；x：real); ｛入栈｝
begin
    s.top:=s.top+1；
    s.data[s.top]:=x
end；
begin    {主程序}
   i:=0;
   repeat
       i:=i+1;  read(a[i]);    {将表达式存入数组a}
   until a[i]=’@’;
   s.top:=0;        {清空栈}
   i:=1;            {i为a数组的下标}
   ch:=a[i];
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:=a[i]; 
  end;
  end;
                 ‘+’: x:=pop(s)+pop(s)
                 ‘-’: begin 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);            {将上面得到的x入栈}
       i:=i+1;ch:=a[i];      {继续扫描a数组}
    end;
  writeln(pop(s))
end.
4、计算后缀表达式的值
编一个程序，输入一个实数中缀表达式（由0-9组成的运算数、加（+）、减（-）、乘（*）、除（/）四种运算符、左右小括号、小数点组成。注意“-”也可作为负数的标志），判断表达式是否合法，如果不合法，请输出“NO”；否则求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值；
     8*-5是不合法的，必须写成8*（-5）；12.和.5也算合法，分别表示12.0和0.5；
[参考程序]
program lx8;
const max=100;
      list_1:set of char=['*','/','+','-','.','(',')','0'..'9'];
      list_2:set of char=['*','/','+','-'];
      number:set of char=['0'..'9'];
      zero=0.0000000001;
var sin,tmp:string;
    result:real;
procedure outerror;
begin
     writeln('No');
     halt;
end;
function error(s:string):boolean;
var i,j,k:longint;
    f:boolean;
begin
     f:=false;
     k:=0;
     for i:=1 to length(s) do
         begin
              if not(s[i] in list_1) then f:=true;
              if (s[i] in list_2)and(s[i-1]in list_2) then f:=true;
              if (s[i]='(')and(s[i-1]=')') then f:=true;
              if s[i]='(' then inc(k);
              if s[i]=')' then dec(k);
         end;
     if k<>0 then f:=true;
     error:=f;
end;
procedure dealwithnegative(var s:string);
var i,j,k:longint;
    tmp:string;
begin
     tmp:='';
     i:=1;
     for i:=1 to length(s) do
         begin
              if  (s[i]='-')and
                  ((i=1)or(s[i-1]='('))then
                  tmp:=tmp+'0';
              tmp:=tmp+s[i];
         end;
     s:=tmp;
end;
function convert(s:string; var i:longint):real;
var r:real;
    tmp:string;
    p:longint;
begin
     tmp:='';
     while (s[i] in number)or(s[i]='.') do
           begin
                tmp:=tmp+s[i];
                inc(i);
           end;
     i:=i-1;
     val(tmp,r,p);
     if p<>0 then outerror;
     convert:=r;
end;
function calc(r1,r2:real; ch:char):real;
begin
     case ch of
          '+':calc:=r1+r2;
          '-':calc:=r1-r2;
          '*':calc:=r1*r2;
          '/':begin
                   if abs(r2)<zero then begin writeln('divided by zero');halt;end;
                   calc:=r1/r2;
              end;
     end;
end;
procedure scan(sin:string;var result:real);
var i,j,top1,top2:longint;
    ovs:array [1..max] of real;
    ops:array [1..max] of char;
    f:array['#'..'/','#'..'/'] of longint;
begin
   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;
  if error(sin) then outerror;
  dealwithnegative(sin);
  sin:=sin+')';
  ops[1]:='(';
  top1:=0; top2:=1; i:=1;
  while i<=length(sin) do
  begin
    if (sin[i] in number)or(sin[i]='.')
      then begin
              top1:=top1+1;
              ovs[top1]:=convert(sin,i);
           end
      else begin
             while f[ops[top2],sin[i]]=1 do
             begin
                ovs[top1-1]:=calc(ovs[top1-1],ovs[top1],ops[top2]);
                top1:=top1-1;
                top2:=top2-1;
             end;
             if f[ops[top2],sin[i]]=0
                then top2:=top2-1
                else begin
                       top2:=top2+1;
                       ops[top2]:=sin[i];
                     end;
            end;
     inc(i);
  end;
  result:=ovs[1];
end;
begin {main}
     write('Input a expression:');
     readln(sin);
     scan(sin,result);
     writeln('The result is: ',result:0:3);
end.
5、单词查找树
[问题描述] 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：
1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；
2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；
3．在满足上述条件下，该单词查找树的结点数最少。
4．例如图6_2左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。
[问题输入]
输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。
[问题输出]
输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。

[样例输入]
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
[样例输出]
13

[算法分析]
首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位……如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加入单词查找树中去。但，本问题只是问你结点总数，而非建树方案，且有32K文件，所以应该考虑能不能通过不建树就直接算出结点数？为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则说单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中已有单词的差的最小值。
单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是，得出建树的等效算法：
① 读入文件；
② 对单词列表进行字典顺序排序；
③ 依次计算每个单词对前一单词的差，并把差累加起来。注意：第一个单词相对于“空”的差为该单词的长度；
④ 累加和再加上1（根结点），输出结果。
就给定的样例，按照这个算法求结点数的过程如下表：
表6_1
原单词列表
排序后的列表
差值
总计
输出
A
A
1
12
13
AN
AN
1
ASP
AS
1
AS
ASC
1
ASC
ASCII
2
ASCII
ASP
1
BAS
BAS
3
BASIC
BASIC
2

[数据结构] 先确定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：array[1..32767] of char；把所有单词连续存放起来，文件中每个单词后的换行符转换成数组中的一个“空格”字符。这样既省略了一个存放单词长度的数组，又方便且节省了一点空间。另外为了排序，再设一个数组index:array[1.. 6700] of integer；存放每个单词在a中的起始位置。这样，排序时用a比较，但只要交换index的值就可以了。
[参考程序]
Program p6_1(Input, Output)；
Var
a:Array[1..32767] Of Char；
index:Array[1..6700] Of Integer；
n,k,i,j,tot,t:Integer；
s,pre,now:String；
Function cmp(i, j:Longint):Boolean；{比较从a[i]开始的字符串和从a[j]开始的字符串
Begin 大小，小于则返回False，否则返回True}
While ((a[i]=a[j]) And (Ord(a[i])<>32) And (Ord(a[j])<>32)) Do
Begin Inc(i)；Inc(j)；End；
If (a[i]<a[j]) Then cmp := False Else cmp := True；
End；
Begin {main}
Assign(Input,'word.in')； Reset(Input)；
Assign(Output,'word.out')；Rewrite(Output)；
Fillchar(a, sizeof(a), 0)；
n := 0；{单词个数}
k := 0；{下标}
While (Not Eof) Do {读入文件中的单词并且存储到数组中}
Begin
Readln(s)；
n := n+1；
index[n] := k+1；{第n个单词的首字母起点下标}
For i:=1 To Length(s) Do {存入一个单词}
a[k+i] := s[i]；
k := k+i+1； {为下个单词的下标设定好初值,i即为当前单词的长度}
End；
For i:=1 To n Do {n个单词的字典排序}
For j:=i+1 To n Do
If cmp(index[i], index[j]) Then
Begin t := index[i]；index[i] := index[j]；index[j] := t；End；
tot := 0； {计数器}
pre := ''； {前一个单词}
For i:=1 To n Do {统计}
Begin
now := ''；
j := index[i]； {第i个单词的首字母在a数组中的下标为j}
While (Ord(a[j])<>0) Do {换行符换成了空格}
Begin now := now + a[j]；j := j+1；End； {当前处理的单词存入now中}
j := 1；
While ((pre[j]=now[j]) And (j<=length(pre))) Do Inc(j)；{求两个单词的差}
tot := tot+(Length(now)-j+1)； {累加}
pre := now；{把当前单词作为下次比较的前一个单词}
End；
Writeln(tot+1)；
Close(Input)；Close(Output)；
End.