题解 P1175 【表达式的转换】

hanmo0321 · 2018-10-14 11:56:39 · 题解

对于我这个蒟蒻来说, 这题有毒...... 我是不会告诉你这题坑了我一上午的

超级华(chou)丽(lou)的分割线

好了，不扯了。这题主要分两步： 1、转后缀表达式 2、递等式计算后缀表达式 转后缀表达式的方法有很多，以下代码采用二叉树后序遍历的方法 还要注意一点，运算符中有^乘方运算,为了省时,我用了快速幂来计算

丑到极限的分割线

下面贴上又臭又长的垃圾代码:

var
    s,st:ansistring;
    len,i,top1,top2,root,j:longint;
    pre:array[chr(1)..chr(127)] of longint;
    s1,s2,l,r:array[0..105] of longint;
procedure dfs(x:longint);//二叉树后序遍历
begin
    if l[x]<>0 then dfs(l[x]);
    if r[x]<>0 then dfs(r[x]);
    st:=st+s[x]+' ';
end;
function quick_pow(a,b:longint):longint;//非递归快速幂
var
    rest:longint;
begin
    rest:=1;
    while b>0 do
    begin
        if b mod 2=1 then rest:=rest*a;
        a:=a*a;
        b:=b>>1;
    end;
    exit(rest);
end;
begin
    readln(s);
    len:=length(s);
    pre['+']:=1;
    pre['-']:=1;
    pre['*']:=2;
    pre['/']:=2;
    pre['^']:=3;//优先级
    for i:=1 to len do
    begin
        if (s[i]>='0')and(s[i]<='9') then
        begin
            inc(top1);
            s1[top1]:=i;
        end
        else
        if s[i]='(' then
        begin
            inc(top2);
            s2[top2]:=i;
        end
        else
        if s[i]=')' then
        begin
            while s[s2[top2]]<>'(' do
            begin
                root:=s2[top2];//寻找根节点
                l[s2[top2]]:=s1[top1-1];
                r[s2[top2]]:=s1[top1];
                top1:=top1-2;
                inc(top1);
                s1[top1]:=s2[top2];
                dec(top2);
            end;
            dec(top2);
        end
        else
        if (s[i]='+')or(s[i]='-')or(s[i]='*')or(s[i]='/')or(s[i]='^') then
        begin
            while (top2>0)and(pre[s[i]]<=pre[s[s2[top2]]]) do
            begin
                root:=s2[top2];
                l[s2[top2]]:=s1[top1-1];
                r[s2[top2]]:=s1[top1];
                top1:=top1-2;
                inc(top1);
                s1[top1]:=s2[top2];
                dec(top2);
            end;
            inc(top2);
            s2[top2]:=i;
        end;
    end;
    while top2>0 do//计算剩下的运算符
    begin
        root:=s2[top2];
        l[s2[top2]]:=s1[top1-1];
        r[s2[top2]]:=s1[top1];
        top1:=top1-2;
        inc(top1);
        s1[top1]:=s2[top2];
        dec(top2);
    end;
    dfs(root);
    writeln(st);
    len:=length(st);
    top1:=0;top2:=0;
    for i:=1 to len do
    begin
        if st[i]=' ' then continue;//过滤空格
        if (st[i]>='0')and(st[i]<='9') then
        begin
            inc(top1);
            s1[top1]:=ord(st[i])-48;
        end
        else
        begin
            if st[i]='+' then
            begin
                s1[top1-1]:=s1[top1-1]+s1[top1];
                dec(top1);
            end
            else
            if st[i]='-' then
            begin
                s1[top1-1]:=s1[top1-1]-s1[top1];
                dec(top1);
            end
            else
            if st[i]='*' then
            begin
                s1[top1-1]:=s1[top1-1]*s1[top1];
                dec(top1);
            end
            else
            if st[i]='/' then
            begin
                s1[top1-1]:=s1[top1-1] div s1[top1];
                dec(top1);
            end
            else
            if st[i]='^' then
            begin   
                s1[top1-1]:=quick_pow(s1[top1-1],s1[top1]);
                dec(top1);
            end;
            for j:=1 to top1 do write(s1[j],' ');
            writeln(copy(st,i+2,len-i-1));//递等式输出
        end;
    end;
end.