后缀转中缀的另一种方法——二叉树的遍历

 

鉴于自己虽然在向总的带领下学了树但是从来都没有用过。

在数据结构的书上，关于二叉树有这样的一段内容：当我们把表达式依照一定的规则，构成一棵树的时候，中序遍历再加一些括号是正常的表达式，后序遍历是逆波兰式。

所以，用逆波兰式构成一棵树，再依照中序遍历的法则，将后缀表达式转为中缀表达式。

构造一棵树不难，主要是添括号的问题。

所以 测了多次，问题总是出现在 compare函数上（程序里成comepare了），

不过感觉这个comepar函数还是比较好写的，相比起 用栈来做。。。。。

主要是减号和除号的问题。。。

program expression;
type
        point=^rec;
        rec=record
            left,right:point;
            ch:char;
                end;
var
        i,j,k,l,m,n:longint;
        st,stt:string;
        h:point;
procedure make(var l:longint;p:point);
var
        i,j,k,m,n:longint;
begin
      if l>=1 then begin
      if(ord(st[l])<65)or(ord(st[l])>90)then
        begin
        p^.ch:=st[l];
        dec(l);
        new(p^.right);
        make(l,p^.right);
        dec(l);
        new(p^.left);
        make(l,p^.left);
        end
      else
        begin
        p^.ch:=st[l];
        p^.left:=nil;
        p^.right:=nil;
        end;
      end;
end;
{===============================================================}
function print(p:point):ansistring;
var
        a,b,c,d:string;
        bool1,bool2:boolean;
        le,ri,mi:char;
function comepare(a,b:char):char;
var
        x,y:longint;
begin
        if(((a='-')and((b='-')or(b='+')))or((a='/') and ((b='/')or(b='*'))))then exit('>');
        case a of
          '+','-':x:=2;
          '*','/':x:=4;
        end;
        case b of
          '+','-':y:=2;
          '*','/':y:=4;
        end;
        if x>y then exit('>')
        else exit('<');
end;
{===============================================================}
begin
        bool1:=true;
        bool2:=true;
     print:='';
     if p^.left<>nil then
        begin
        le:=p^.left^.ch;
        ri:=p^.right^.ch;
        mi:=p^.ch;
        if(ord(le)>=65)and(ord(le)<=90)then bool1:=false;
        if(ord(ri)>=65)and(ord(ri)<=90)then bool2:=false;
        begin
        if(comepare(mi,le)='>')and((mi<>'-')or((le<>'-')and(le<>'+')))and((mi<>'/')or((le<>'/')and(le<>'*')))and bool1 then
                begin
                a:='('; b:=')';
                end
                else
                begin
                a:='';b:='';
                end;
        if (comepare(mi,ri)='>')and bool2 then
                begin
                c:='('; d:=')';
                end
                else
                begin
                c:='';d:='';
                end;
        print:=a+print(p^.left)+b+mi+c+print(p^.right)+d;
        end
        end
        else exit(p^.ch);
end;
begin
        assign(input,'expression.in');
        assign(output,'expression.out');
        reset(input);
        rewrite(output);
        readln(st);
        l:=length(st);
        new(h);
        make(l,h);
        stt:=print(h);
        write(stt);
        close(input);
        close(output);
end.