记录编号	18487	评测结果	AAAAAAAAAA
题目名称	表达式转换	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2010-09-15 13:33:57	内存使用	0.28 MiB

Program BDtree (Input, Output);

Uses
  Math;

Type
  P_re= ^re;
  re=
  Record
    data: Char;
    left, right: P_re;
  End;

Var
  expr, hou: String;
  arr, i, j: Longint;
  num: Array[1..10000] Of Longint;
  outl: P_re;

Function Calcn (ch: Char; a, b: Longint): Longint;
  Begin
    Case ch Of
      '+': Exit(a+b);
      '-': Exit(a-b);
      '*': Exit(a*b);
      '/': Exit(a div b);
      '^': Exit(Trunc(Intpower(a,b)));
    End;
  End;

Function Calc (expr: String): P_re;
  Var
    ns: Array [1..1000] Of P_re;
    os: Array [1..1000] Of Char;
    code: Longint;
    tmp: P_re;
    i, nsn, osn, bas: Cardinal;
    ts: String;

  Function YXJ (c:char): Byte;
  Begin
    Case c Of
      '+', '-': YXJ:=0;
      '*', '/': YXJ:=1;
      '^': YXJ:=2;
    End;
  End;

  Function Copr (op: Char; a, b: P_re):P_re;
  Var
    ans: P_re;
  Begin
    New (ans);
    ans^.data:=op;
    ans^.left:=a;
    ans^.right:=b;

    Copr:=ans;
  End;

  Begin
    i:=1;
    nsn:=0;
    osn:=0;

    While i<=Length(expr) Do
    Begin
      If expr[i] in ['0'..'9'] Then
      Begin
        Inc(nsn);

        New(ns[nsn]);

        ns[nsn]^.data:=expr[i];
        ns[nsn]^.left:=NIL;
        ns[nsn]^.right:=NIL;
      End
      Else If expr[i] in ['+','-','*','/','^'] Then
      Begin
        If osn>0 Then
          While (osn>0) AND (YXJ(os[osn]) >= YXJ(expr[i])) Do
          Begin
            New(tmp);
            tmp:=Copr(os[osn],ns[nsn-1],ns[nsn]);
            ns[nsn-1]:=tmp;
            Dec(osn);
            Dec(nsn);
          End;

        Inc(osn);
        os[osn]:=expr[i];
      End
      Else If expr[i] IN ['(',')'] Then
      Begin
        bas:=1;
        ts:='';
        Repeat
          Inc(i);

          ts:=ts+expr[i];

          If expr[i]='(' Then Inc(bas);
          If expr[i]=')' Then Dec(bas);
        Until (expr[i]=')') AND (bas=0);

        Delete(ts, Length(ts), 1);
        Inc(nsn);
        ns[nsn]:=Calc(ts);
      End;

      Inc(i);
    End;

    While osn>0 Do
    Begin
      New(tmp);
      tmp:=Copr(os[osn],ns[nsn-1],ns[nsn]);
      ns[nsn-1]:=tmp;
      Dec(osn);
      Dec(nsn);
    End;

    Calc:=ns[1];
  End;

Procedure Prnstr (add: P_re);
  Begin
    If add^.left<>NIL Then
      Prnstr(add^.left);

    If add^.right<>NIL Then
      Prnstr(add^.right);

    hou:=hou+add^.data;
  End;

Begin
  Assign(Input, 'express.in');
  Reset(Input);

  Assign(Output, 'express.out');
  Rewrite(Output);

  Readln(expr);

  outl:=Calc(expr);

  Prnstr(outl);

  For i:=1 To Length(hou) Do
    Write(hou[i],' ');
  Writeln;

  for i:=1 To Length(hou) Do
    If hou[i] in ['0'..'9'] Then
    Begin
      Inc(arr);
      num[arr]:=Ord(hou[i])-48;
    End
    Else
    Begin
      num[arr-1]:=Calcn(hou[i],num[arr-1],num[arr]);
      Dec(arr);

      For j:=1 To arr Do
        Write(num[j],' ');

      For j:=i+1 To Length(hou) Do
        Write(hou[j],' ');

      Writeln;
    End;

  Close(Input);
  Close(Output);
End.