#import std
#import nat

#comment -[
The input file contains an infix algebraic expression consisting of
non-negative integers, parentheses, single-letter identifiers, and the
arithmetic operators +,-,*, and / with standard precedence. The output
is an equivalent expression in prefix notation.  For example, the
input 3 * x + ( 9 + y ) / 4 becomes (+ (* 3 x) (/ (+ 9 y) 4)). The -r
option requests simplification via constant folding, factoring, and
cancellation. The simplified form may be a refinement the original in
cases where it is undefined due to division by zero. E.g., 1/(1/x)
simplifies to x.

Copyright (C) 2007 Dennis Furey]-

#optimize+

parse = # takes a list of character strings containing an expression to a parse tree with syntax checking

mat` ; sep` ; ~&F; (rlc both -=digits)*=; -+
   ~&i&& -+
      `(?=itthrdh4BB/<'unbalanced parenthesis'>!% ~&tZhlPZB?/~&hr <'assertion failure'>!%,
      -&~&titBP,~&thl,~&thrdh-='+-*/'&--> ~&Nthrd3tthr3hrPNCCVXttt2C+-,
   %tsTXLMk+ ~&NiX; ~&r->l ^\~&rt '+-*/)'?<rhh(
      ~&lihlPZB?\(% ~&iNC+ 'misplaced operator: '--+ ~&rh) cases~&rhh\~&NNXrhPNVXlC {
         '+-': ~&NNXrhPNVXlC+ -&~&ltitBP,~&lthl,~&lthrdh-='-*/'&--> ~&lNthrd3tthr3hrPNCCVXttt2CPrX,
         '*/': ~&NNXrhPNVXlC+ -&~&ltitBP,~&lthl,~&lthrdh-='/'&--> ~&lNthrd3tthr3hrPNCCVXttt2CPrX,
         ')': ~&l; -+
            `(?=itthrdh4BB/~&httPC <'unbalanced parenthesis'>!%,
            -&~&titBP,~&thl,~&thrdh-='+-*/'&--> ~&Nthrd3tthr3hrPNCCVXttt2C+-},
      -!~&lZ,~&lhl!-?/^C(^\~&rhPNV ~&rhh==`(,~&l) % ~&iNC+ 'missing operator before '--+ ~&rh)+-

canonical_form = # flattens products and sums and converts subtraction and division to unary minus and inversion

-+
   ^= (*^0 '+*'?<dh\~& ~&ddvDlrdPErvPrNCQSL2V); %sTCRk ~&av^?\~&a cases~&adhPvhd2C\~&adPfavPMV {
      {'--','//'}: ~&favhvh4R,
      {'-+','/*'}: ~&avhd3fadvhv2DlrNCVS2MV,
      {'-*'}: (~&rr?\~&la %sTJsTLWXCk ~&lavhd4rlPlfPlad2rrh2NCVRrrt2CTV)^/~& ~&avhv; != ~&dh-=digits},
   *^0 '-/'?<dh\~& ^V\~&vhPdvtPVNCC '-'?=d/'+'! '*'!+-

binary_form = # restores binary arity to a parse tree (opposite of canonical_form)

-+
   -++- ~&H\<'+-','*/'> * ~&iNCS; <"+","-">. ^= ^?(
      -&~&ad=="-",~&av,~&avthd=="+"&-,
      ~&\~&adPfavPMV ~&adPfadPavh2avthvh5NCCVRfavthvth6RNCCV),
   ~&i&& ~&dvvZvtPYivhPQSPVo; ~&av^?\~&a ~&avt?\~&favh2R ~&adPfavh2RfadvtPVPRNCCV,
   -++- ~&H\<'-0','/1'> * ~&iNCS; <"-","0">. *^0 -&~&d=="-",~&vtZ&-?\~& ^V/~&d :/("0"^:<>)+ ~&v,
   -++- ~&H\<'+-0','*/1'> * ~&iNCS; <"+","-","0">. "+"^?=ad\~&adPfavPMV -+
      ~&rr?\~&lrlPV ~&rl?/~&rrhd3rlt2lrlPVrlh2Qrrt2lrrvhPS2Vrrhvh4QNCCV ^V/~&rrhd :/("0"^:<>)+ ~&rrt2lrrvhPS2Vrrhvh4QNC,
      ^/~&ad %sTLWMk+ ^JfalPMfarPMX/~&f ~&d=="-"!=rlX+ ~&av+-+-

constant_folding = # collects and evaluates constant subtrees in a parse tree in canonical form

(*^0 '+*'?<dh\~& ~&ddvDlrdPErvPrNCQSL2V)+ -++- *^0* <
   '+'?=d\~& ^rtPlrVrhPQ/~&d ~&v; ||<'0'^: <>>! ~&d~='0'*~,
   ||~& ~&d=='*'&& ^rrtPlrVrhPQB/~&d (~&v; != ~&d=='/'&& ~&vhdh-=digits); ~&litZB&& -+
      ~&r!=; ~&l&& :^/~&lhr ~&ltlS2rlSPT,
      ^D(%np+ ~&lhvhdNC,~&r); * ^/~&r ~&rd=='+'&& ^rlrVB/~&rd -+
         ~&lirZBPg&& * -?~&rdh-=digits: ~&lNV,~&rvhdh-=digits: &rvhd:=r ~&l,&rvhvhd:=r ~&l?-^|lhPrX/%nP+~&l ~&,
         ^p\~&rv ~&lrvPD; * -&~&rdh-=digits,~&l,division^\~&l %np+ ~&rdNC&-+ '*'?=rd(~&lrvh2X,~&)+ '-'?=rd/~&lrvh2X ~&+-+-,
   -&~&d=='*',~&vhdh-=digits&-?\~& -+
      ~&rl?\~&l ^rtPlrVrhPQ/~&ld :^\~&rltPrT ^V/~&rlhd ~&lvhd3rlhv3D; * -?
         -&~&rd=='*',~&rvhdh-=digits&-: &rvhd:=r ~&h+ %nP+ product+ %np~~+ ~&lrvhd3XbiNC,
         -&~&rd=='-', ~&rvh; -&~&d=='*',~&vhdh-=digits&-&-: &rvhvhd:=r ~&h+ %nP+ product+ %np~~+ ~&lrvhvhd5XbiNC,
         '*'^:+ ~&lNVrNCC?-,
      ^/~& ~&vt; != ~&d=='+'&& ~&v; !=rZrtPZY '-'?=d(~&vh,~&); ~&d=='*'&& ~&vh; ~&dh-=digits+-,
   ^V(~&d,~&v; -< ~&ldh-=digits!| lleq+~&bd); '*'?=d\~& -+
      ~&rlihB?\~&rrt2lrrPVrrh2Q ~&V/'-'+ ~&rrt2lrrPVrrh2QNC,
      ^/~&d ~&v; ^(
         length+ *~ ~&d=='-'+ '/'?=d/~&vh ~&,
         ||<'1'^: <>>! ~&d~='1'*~+ * '-'?=d/~&vh -&~&d=='/',~&vhd=='-'&-?/~&dvhv2V ~&)+-,
   '*'?=d\~& ^rtPlrVrhPQ/~&d ~&v; -+
      -&subset/<'0'^: <>,'/'^: <'0'^: <>>>&-?l/<'0'^: <>,'/'^: <'0'^: <>>>! ^|T\~& ~&i&& -+
         ('1'?=thvhd/~&hNC ~&)^lrNCC(~&r,~&lrNCV/'/'+ ~&l)+ ~~ ~&hNV+ %nP,
         quotient^~brlXPlrGO(gcd,~&)+ product:-1~~+ %np~*+ (=='/')!=lvhPSPrXbdNCS&d+-,
      != ~&dh-=digits!| ~&d=='/'&& ~&vhdh-=digits+-,
   '+'?=d\~& ^rtPlrVrhPQ/~&d ~&v; -+
      ~&l?\~&r ^|T\~& -+
         (~&l?\~&rNC ~&VNC/'-'+ ~&rNC)^|/~& ~&hNV+ %nP,
         nleq?(~&NiX+ difference+ ~&rlX,~&/&+ difference)+ sum:-0~~+ %np~*+ (=='-')!=lvhPSPrXbdNCS&d+-,
      != ~&dh-=digits!| ~&d=='-'&& ~&vhdh-=digits+->

cancellation = # accumulates coefficients

-++- *^0* <
   '-'?=d\~& '0'?=vhd\~& ~&vh,
   '/-'?<dh\~& ~&dvhd2E?/~&vhvh ~&,
   ||~& &&~&vh ==('/'^: <'1'^: <>>),
   '*'?=d\~& '0'?=vhd\~& ||~& ~&v; &&~&h //~< '/'^: <'0'^: <>>,
   '*'?=d\~& ~&?(~&t?\~&h '*'^:,! '1'^: <>)+ ~&v; -+
      ^|T\~& *= -+
         (~&l?\~&r '/'^:*+ ~&riNCS)^/~&ll ^DlS/~&r iota+ ~&lr,
         ^(^|(~&,difference)^llrrlXPXiQ(nleq,~&)+ length~~+ !=rlX ~&d=='/',~&h; '/'?=d/~&vh ~&)+-,
      ~&t!=lrhSPX+ |= (==&& ~&ld~='0')+ ~~ '/'?=d/~&vh ~&+-,
   '+'?=d\~& ~&?(~&t?\~&h '+'^:,! '0'^: <>)+ ~&v; -+
      ^|T\~& *= (~&lr&& ~&iNC+ (~&l?\~&r '-'^:+ ~&rNC)^/~&ll 1?=lr/~&r '*'^:+ ^lrNCC\~&r ~&hNV+ %nP+ ~&lr)^(
         ~&d=='-'!=rlvhPSPX; -+
            ^|(~&,difference)^llrrlXPXiQ/nleq ~&,
            ~~ sum:-0+ * -&~&d=='*',~&vhdh-=digits&-?\1! %np+ ~&vhdNC+-,
         ~&h; -&~&d=='*',~&vhdh-=digits&-?(~&vtt2dvtPVvth2Q,~&)+ '-'?=d/~&vh ~&),
      %sTLLsTLXMk+ ~&t!=lrhSPX+ |= ==+ ~~ -&~&d=='*',~&vhdh-=digits&-?(~&vtt2dvtPVvth2Q,~&)+ '-'?=d/~&vh ~&+->

factoring = # extracts common terms from a sum of products

*^0 '*'?=d/~&ddvDlrdPErvPrNCQSL2V '+'?=d\~& ^rtPlrVrhPQ/~&d ~&v; ^rlPlTrrPj/~& -+
   ^\~&rSL * '*'^:+ ^lrNCC/~&l (~&t?\~&h '+'^:)+ -*; * -+
      (~&l?\~&r '-'^:+ ~&rNC)^|/~& ==?/('1'^: <>)! &rv:=rvtPivhPQ gldif~&E+ ~&rvPlNCX,
      ^rlPlrrPXX/~&l '-'?=rd/~&NNXrvh2X ~&NrX+-,
   (~&NiX; ~&rrhr2lrSL2cZB->l ~&rhPlCrtPX)+ ~&rtPF+ * ^/~&l ~| -!==,~&rd=='*'&& ~&lrvPw!-^|/~& '-'?=d/~&vh ~&,
   ^DrlXS/~& ~&s+ *= '*'?=d(~&v,~&iNC)+ '-'?=d(~&vh,~&)+-

#executable <'par',''>

prefixer =

~&iNC+ file$[contents: --<''>]+ ~command; -|
   ~&iiNCB+ -+
      *^0 ~&v?\~&d :/`(+ --')'+ ^|T/~& :/` + mat` ,
      ~&l?\~&r ~&r; binary_form+ canonical_form; ^= factoring+ cancellation+ constant_folding,
      ^(~&w/'r'+ ~keyword*+ ~options,~files; ~&i&& parse+ ~&h.contents)+-,
   ! <'usage: prefixer inputfile [-r]'>|-