math.sed revision 228975
1128785Ssmkelly# This is ksb's infamous sed calculator. (ksb@sa.fedex.com) 21590Srgrimes# 3128785Ssmkelly# $FreeBSD: head/tools/regression/usr.bin/sed/math.sed 228975 2011-12-30 00:04:11Z uqs $ 41590Srgrimes# 5128785Ssmkelly# $Id: math.sed,v 2.5 1998/08/02 13:23:34 ksb Exp ksb $ 6128785Ssmkelly# expr ::= (expr) | expr! | 7128785Ssmkelly# expr ^ expr | 8128785Ssmkelly# -expr | expr * expr | expr / expr | expr % expr | 9128785Ssmkelly# expr + expr | expr - expr | 10128785Ssmkelly# [0-9][0-9]* ; 11128785Ssmkelly# Bugs: some sign combinations don't work, and I got sick of added cases 12128785Ssmkelly# for unary +. Don't depend on signed math working all the time. -- ksb 131590Srgrimes# 14128785Ssmkelly# $Compile: echo "4+7*3+2^7/3" | sed -f %f 151590Srgrimes 161590Srgrimes# make sure the expression is well formed 171590Srgrimess/[ ]//g 18128785Ssmkelly/[*\/^%+-]$/{ 191590Srgrimes a\ 20128785Ssmkelly poorly formed expression, dyadic operator on the end 211590Srgrimes q 221590Srgrimes} 23128785Ssmkelly/^[*\/^%]/{ 241590Srgrimes a\ 25128785Ssmkelly poorly formed expression, leading dyadic operator 261590Srgrimes q 271590Srgrimes} 281590Srgrimes 291590Srgrimes# fill hold space with done token 301590Srgrimesx 311590Srgrimess/^.*/done/ 321590Srgrimesx 331590Srgrimes 34128785Ssmkelly# main loop, process operators ((), !, *, /, %, +, and -) 351590Srgrimes: loop 36128785Ssmkelly# uncomment the print below to follow the "logic" -- ksb 37128785Ssmkelly#p 38128785Ssmkelly/^[+]/{ 391590Srgrimes s/// 401590Srgrimes b loop 411590Srgrimes} 42128785Ssmkelly/^--/{ 43128785Ssmkelly s/// 44128785Ssmkelly b loop 45128785Ssmkelly} 46128785Ssmkelly# eval parenthesised sub expressions first 471590Srgrimes/^\(.*\)(\([^)]*\))\(.*\)$/{ 481590Srgrimes H 491590Srgrimes s//\2/ 501590Srgrimes x 511590Srgrimes s/^\(.*\)\n\(.*\)(\([^()]*\))\(.*\)$/()\2@\4@\1/ 521590Srgrimes x 531590Srgrimes b loop 541590Srgrimes} 55128785Ssmkelly# reduce a^b^c -> a^(b^c) 56128785Ssmkelly/\([0-9][0-9]*^\)\([0-9][0-9]*^[0-9][0-9^]*\)/{ 57128785Ssmkelly s//\1(\2)/ 581590Srgrimes b loop 591590Srgrimes} 60228975Suqs# pull any buried exponents 61128785Ssmkelly/^\(.*[^0-9]\)\([0-9][0-9]*^[0-9][0-9]*\)$/{ 62128785Ssmkelly s//\1(\2)/ 63128785Ssmkelly b loop 64128785Ssmkelly} 65128785Ssmkelly/^\(.*[^0-9]\)\([0-9][0-9]*^[0-9][0-9]*\)\([^0-9].*\)$/{ 66128785Ssmkelly s//\1(\2)\3/ 67128785Ssmkelly b loop 68128785Ssmkelly} 69128785Ssmkelly/^\([0-9][0-9]*^[0-9][0-9]*\)\([^0-9].*\)$/{ 70128785Ssmkelly s//(\1)\2/ 71128785Ssmkelly b loop 72128785Ssmkelly} 73128785Ssmkelly/^\([-]*[0-9]*\)^0*$/{ 74128785Ssmkelly s//1/ 75128785Ssmkelly b loop 76128785Ssmkelly} 77128785Ssmkelly/^\([-]*[0-9]*\)^0*1$/{ 78128785Ssmkelly s//\1/ 79128785Ssmkelly b loop 80128785Ssmkelly} 81128785Ssmkelly/^\([-]*[0-9]*\)^-[0-9]*$/{ 82128785Ssmkelly s//0/ 83128785Ssmkelly b loop 84128785Ssmkelly} 85128785Ssmkelly/^\([-]*\)\([0-9]*\)^\([0-9][0-9]*[13579]\)$/{ 86128785Ssmkelly s//\1\2*((\2*\2)^(\3\/2))/ 87128785Ssmkelly b loop 88128785Ssmkelly} 89128785Ssmkelly/^[-]*\([0-9]*\)^\([0-9][0-9]*[02468]\)$/{ 90128785Ssmkelly s//(\1*\1)^(\2\/2)/ 91128785Ssmkelly b loop 92128785Ssmkelly} 93128785Ssmkelly# single digit powers (2 3,9 4,6,8 5,7 94128785Ssmkelly/^[-]*\([0-9]*\)^0*2$/{ 95128785Ssmkelly s//(\1*\1)/ 96128785Ssmkelly b loop 97128785Ssmkelly} 98128785Ssmkelly/^\([-]*\)\([0-9]*\)^0*\([39]\)$/{ 99128785Ssmkelly s//\1(\2*(\2*\2))^(\3\/3)/ 100128785Ssmkelly b loop 101128785Ssmkelly} 102128785Ssmkelly/^[-]*\([0-9]*\)^0*\([468]\)$/{ 103128785Ssmkelly s//(\1*\1)^(\2\/2)/ 104128785Ssmkelly b loop 105128785Ssmkelly} 106128785Ssmkelly# 5 7 107128785Ssmkelly/^\([-]*[0-9]*\)^\([0-9]*\)$/{ 108128785Ssmkelly s//\1*(\1^(\2-1))/ 109128785Ssmkelly b loop 110128785Ssmkelly} 111128785Ssmkelly# reduce all number factorials 112128785Ssmkelly/^0*[01]!/{ 113128785Ssmkelly s//1/ 114128785Ssmkelly b loop 115128785Ssmkelly} 116128785Ssmkelly/\([*+-/%^]\)0*[01]!/{ 117128785Ssmkelly s//\11/ 118128785Ssmkelly b loop 119128785Ssmkelly} 120128785Ssmkelly/\([0-9]*\)!/{ 121128785Ssmkelly s//(\1-1)!*\1/ 122128785Ssmkelly b loop 123128785Ssmkelly} 124128785Ssmkelly# sign simplifications 125128785Ssmkelly/^-\([0-9]*\)\([*/%]\)-\([0-9]*\)$/{ 126128785Ssmkelly s//\1\2\3/ 127128785Ssmkelly b loop 128128785Ssmkelly} 129128785Ssmkelly/^\([0-9]*\)\([*/%]\)-\([0-9]*\)$/{ 130128785Ssmkelly s//-\1\2\3/ 131128785Ssmkelly b loop 132128785Ssmkelly} 133128785Ssmkelly/^-\([0-9][0-9]*\)[+]*-\([0-9][0-9]*\)$/{ 134128785Ssmkelly s//\1+\2/ 135128785Ssmkelly x 136128785Ssmkelly s/\(.*\)/()-@@\1/ 137128785Ssmkelly x 138128785Ssmkelly b loop 139128785Ssmkelly} 140128785Ssmkelly/^-\([0-9]*\)[+]\([0-9]\)*$/{ 141128785Ssmkelly s//\2-\1/ 142128785Ssmkelly b loop 143128785Ssmkelly} 144128785Ssmkelly/^-.*[-+*/%].*/{ 145128785Ssmkelly H 146128785Ssmkelly s/^-// 147128785Ssmkelly x 148128785Ssmkelly s/^\(.*\)\n-.*$/()-@@\1/ 149128785Ssmkelly x 150128785Ssmkelly b loop 151128785Ssmkelly} 152128785Ssmkelly# can we simplify multiplications 153128785Ssmkelly/^\([0-9]*\)\([*][0-9]*[1-9]\)00*$/{ 154128785Ssmkelly H 155128785Ssmkelly s//\1\2/ 156128785Ssmkelly x 157128785Ssmkelly s/^\(.*\)\n[0-9]*[*][0-9]*[1-9]\(00*\)$/()@\2@\1/ 158128785Ssmkelly x 159128785Ssmkelly b loop 160128785Ssmkelly} 161128785Ssmkelly/^\([0-9][1-9]*\)00*\([*][0-9]*\)$/{ 162128785Ssmkelly H 163128785Ssmkelly s//\1\2/ 164128785Ssmkelly x 165128785Ssmkelly s/^\(.*\)\n[0-9][1-9]*\(00*\)[*][0-9]*$/()@\2@\1/ 166128785Ssmkelly x 167128785Ssmkelly b loop 168128785Ssmkelly} 169128785Ssmkelly# can we simplify division (20/30 -> 2/3) 170128785Ssmkelly/^\([0-9][0-9]*\)0\([/%]\)\([0-9][0-9]*\)0$/{ 171128785Ssmkelly s//\1\2\3/ 172128785Ssmkelly b loop 173128785Ssmkelly} 174128785Ssmkelly# n/1 -> n 175128785Ssmkelly/^0*\([0-9][0-9]*\)0[/]0*1$/{ 176128785Ssmkelly s//\1/ 177128785Ssmkelly b loop 178128785Ssmkelly} 179128785Ssmkelly# n%2 -> last_digit(n)%2 (same for 1, BTW) N.B. NO LOOP 180128785Ssmkelly/^[0-9]*\([0-9]\)%0*\([12]\)$/{ 181128785Ssmkelly s//\1%\2/ 182128785Ssmkelly} 183128785Ssmkelly# move any mul/divs to the front via parans 184128785Ssmkelly/^\([0-9+]*\)\([-+]\)\([0-9]*[*/][0-9*/]*\)/{ 185128785Ssmkelly s//\1\2(\3)/ 186128785Ssmkelly b loop 187128785Ssmkelly} 188128785Ssmkelly# can we div or mul 189128785Ssmkelly/^[0-9]*[*][0-9]*$/{ 190128785Ssmkelly b mul 191128785Ssmkelly} 192128785Ssmkelly/^[0-9]*[/%]0*$/{ 193128785Ssmkelly i\ 194128785Ssmkellydivide by zero 195128785Ssmkelly d 196128785Ssmkelly} 197128785Ssmkelly/^[0-9]*[/%][0-9]*$/{ 198128785Ssmkelly H 199128785Ssmkelly s/\([0-9]\).*[/%]/\1-/ 200128785Ssmkelly x 201128785Ssmkelly s/^\(.*\)\n\([0-9]\)\([0-9]*\)\([/%]\)\([0-9]*\).*$/.\4\3q0r\2-\5@\1/ 202128785Ssmkelly x 203128785Ssmkelly b loop 204128785Ssmkelly} 205128785Ssmkelly/^\([0-9]*[*/%][0-9]*\)\(.*\)/{ 206128785Ssmkelly H 207128785Ssmkelly s//\1/ 208128785Ssmkelly x 209128785Ssmkelly s/^\(.*\)\n\([0-9]*[*/][0-9]*\)\(.*\)$/()@\3@\1/ 210128785Ssmkelly x 211128785Ssmkelly b loop 212128785Ssmkelly} 213128785Ssmkelly# can we add or subtract -- note subtract hold expression for underflow 214128785Ssmkelly/^[0-9]*[+][0-9]*$/{ 2151590Srgrimes s/$/=/ 2161590Srgrimes b add 2171590Srgrimes} 218128785Ssmkelly/^[0-9][0-9]*-[0-9]*$/{ 219128785Ssmkelly H 220128785Ssmkelly s/$/=/ 221128785Ssmkelly b sub 222128785Ssmkelly} 223128785Ssmkelly/^\([0-9][0-9]*[-+][0-9]*\)\(.*\)/{ 224128785Ssmkelly H 225128785Ssmkelly s//\1/ 226128785Ssmkelly x 227128785Ssmkelly s/^\(.*\)\n\([0-9]*[-+][0-9]*\)\(.*\)$/()@\3@\1/ 228128785Ssmkelly x 229128785Ssmkelly b loop 230128785Ssmkelly} 231128785Ssmkelly# look in hold space for stack to reduce 2321590Srgrimesx 2331590Srgrimes/^done$/{ 2341590Srgrimes x 235128785Ssmkelly s/^0*\([0-9][0-9]*\)/\1/ 2361590Srgrimes p 2371590Srgrimes d 2381590Srgrimes} 239128785Ssmkelly# .[/%] numerator q quotient r remainder-divisor @stack 240128785Ssmkelly/^\./{ 241128785Ssmkelly x 242128785Ssmkelly /^[^-]/{ 243128785Ssmkelly H 244128785Ssmkelly x 245128785Ssmkelly s/.\(.\)\([0-9]*\)q\([^r]*\)r\([0-9]*\)-\([0-9]*\)@\(.*\)\n\(.*\)/.\1\2q\3+1r\7-\5@\6/ 246128785Ssmkelly h 247128785Ssmkelly s/..[0-9]*q[^r]*r\([0-9]*-[0-9]*\)@.*/\1/ 248128785Ssmkelly b loop 249128785Ssmkelly } 250128785Ssmkelly /^-/{ 251128785Ssmkelly g 252128785Ssmkelly /.\(.\)\([0-9]\)\([0-9]*\)q\([^r]*\)r0*\([0-9]*\)-\([^@]*\)@.*/{ 253128785Ssmkelly s//\5\2-\6/ 254128785Ssmkelly x 255128785Ssmkelly s/.\(.\)\([0-9]\)\([0-9]*\)q\([^r]*\)r0*\([0-9]*\)-\([0-9]*\)@\(.*\)/.\1\3q(\4)*10r\5\2-\6@\7/ 256128785Ssmkelly x 257128785Ssmkelly b loop 258128785Ssmkelly } 259128785Ssmkelly# no digits to shift on 260128785Ssmkelly s/^\.[/]q\([^r]*\)r[^@]*@.*/\1/ 261128785Ssmkelly s/^\.[%]q[^r]*r0*\([0-9][0-9]*\)-[^@]*@.*/\1/ 262128785Ssmkelly /^\./{ 263128785Ssmkelly i\ 264128785Ssmkellydivide error 265128785Ssmkelly q 266128785Ssmkelly } 267128785Ssmkelly x 268128785Ssmkelly s/^\.[/%]q[^r]*r[^@]*@\(.*\)/\1/ 269128785Ssmkelly x 270128785Ssmkelly b loop 271128785Ssmkelly } 272128785Ssmkelly} 2731590Srgrimes/^()/{ 2741590Srgrimes s/// 2751590Srgrimes x 2761590Srgrimes G 2771590Srgrimes s/\(.*\)\n\([^@]*\)@\([^@]*\)@\(.*\)/\2\1\3/ 2781590Srgrimes x 2791590Srgrimes s/[^@]*@[^@]*@\(.*\)/\1/ 2801590Srgrimes x 2811590Srgrimes b loop 2821590Srgrimes} 2831590Srgrimesi\ 284128785Ssmkellyhelp, stack problem - the hold space 2851590Srgrimesp 2861590Srgrimesx 287128785Ssmkellyi\ 288128785Ssmkellyand the pat space 2891590Srgrimesp 290128785Ssmkellyi\ 291128785Ssmkellyquit 2921590Srgrimesq 2931590Srgrimes 294128785Ssmkelly# turn mul into add until 1*x -> x, 0*x -> 0 2951590Srgrimes: mul 296128785Ssmkelly/^00*\*.*/{ 297128785Ssmkelly s//0/ 298128785Ssmkelly b loop 299128785Ssmkelly} 3001590Srgrimes/^0*1\*/{ 3011590Srgrimes s/// 302128785Ssmkelly: leading 303128785Ssmkelly s/^0*\([0-9][0-9]*\)/\1/ 3041590Srgrimes b loop 3051590Srgrimes} 306128785Ssmkellys/^\([0-9]*\)0\*\([0-9]*\)/\1*\20/ 307128785Ssmkellys/^\([0-9]*\)1\*\([0-9]*\)/\1*\20+\2/ 308128785Ssmkellys/^\([0-9]*\)2\*\([0-9]*\)/\1*\20+(\2+\2)/ 309128785Ssmkellys/^\([0-9]*\)3\*\([0-9]*\)/\1*\20+(\2+\2+\2)/ 310128785Ssmkellys/^\([0-9]*\)4\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2)/ 311128785Ssmkellys/^\([0-9]*\)5\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2)/ 312128785Ssmkellys/^\([0-9]*\)6\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2)/ 313128785Ssmkellys/^\([0-9]*\)7\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2)/ 314128785Ssmkellys/^\([0-9]*\)8\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2+\2)/ 315128785Ssmkellys/^\([0-9]*\)9\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2+\2+\2)/ 316128785Ssmkelly/^0*\*[0-9]*[+]*\(.*\)/{ 317128785Ssmkelly s//\1/ 318128785Ssmkelly b loop 3191590Srgrimes} 3201590Srgrimesb mul 3211590Srgrimes 3221590Srgrimes# get rid of a plus term until 0+x -> x 3231590Srgrimes: add 324128785Ssmkelly/^[+]\([0-9+*]*\)=/{ 3251590Srgrimes s//\1/ 326128785Ssmkelly b leading 3271590Srgrimes} 328128785Ssmkelly/^\([0-9*]*\)[+]=/{ 3291590Srgrimes s//\1/ 3301590Srgrimes b loop 3311590Srgrimes} 332128785Ssmkelly/^\([0-9]*\)0[+]\([0-9]*\)\([0-9]\)=/{ 3331590Srgrimes s//\1+\2=\3/ 3341590Srgrimes b add 3351590Srgrimes} 336128785Ssmkelly/^\([0-9]*\)\([0-9]\)[+]\([0-9]*\)0=/{ 3371590Srgrimes s//\1+\3=\2/ 3381590Srgrimes b add 3391590Srgrimes} 340128785Ssmkellys/^\([0-9]*\)1[+]/\10+/ 341128785Ssmkellys/^\([0-9]*\)2[+]/\11+/ 342128785Ssmkellys/^\([0-9]*\)3[+]/\12+/ 343128785Ssmkellys/^\([0-9]*\)4[+]/\13+/ 344128785Ssmkellys/^\([0-9]*\)5[+]/\14+/ 345128785Ssmkellys/^\([0-9]*\)6[+]/\15+/ 346128785Ssmkellys/^\([0-9]*\)7[+]/\16+/ 347128785Ssmkellys/^\([0-9]*\)8[+]/\17+/ 348128785Ssmkellys/^\([0-9]*\)9[+]/\18+/ 3491590Srgrimes 3501590Srgrimess/9=\([0-9]*\)$/_=\1/ 3511590Srgrimess/8=\([0-9]*\)$/9=\1/ 3521590Srgrimess/7=\([0-9]*\)$/8=\1/ 3531590Srgrimess/6=\([0-9]*\)$/7=\1/ 3541590Srgrimess/5=\([0-9]*\)$/6=\1/ 3551590Srgrimess/4=\([0-9]*\)$/5=\1/ 3561590Srgrimess/3=\([0-9]*\)$/4=\1/ 3571590Srgrimess/2=\([0-9]*\)$/3=\1/ 3581590Srgrimess/1=\([0-9]*\)$/2=\1/ 3591590Srgrimes/_/{ 3601590Srgrimes s//_0/ 3611590Srgrimes : inc 3621590Srgrimes s/9_/_0/ 3631590Srgrimes s/8_/9/ 3641590Srgrimes s/7_/8/ 3651590Srgrimes s/6_/7/ 3661590Srgrimes s/5_/6/ 3671590Srgrimes s/4_/5/ 3681590Srgrimes s/3_/4/ 3691590Srgrimes s/2_/3/ 3701590Srgrimes s/1_/2/ 3711590Srgrimes s/0_/1/ 372128785Ssmkelly s/[+]_/+1/ 3731590Srgrimes /_/b inc 3741590Srgrimes} 3751590Srgrimesb add 376128785Ssmkelly 377128785Ssmkelly# get rid of a sub term until /-0*=/ or underflow 378128785Ssmkelly: sub 379128785Ssmkelly/^\([0-9]*\)-0*=/{ 380128785Ssmkelly s//\1/ 381128785Ssmkelly x 382128785Ssmkelly s/\(.*\)\n.*$/\1/ 383128785Ssmkelly x 384128785Ssmkelly b leading 385128785Ssmkelly} 386128785Ssmkelly/^-\([0-9].*\)=/{ 387128785Ssmkelly: under 388128785Ssmkelly g 389128785Ssmkelly s/.*\n\([0-9]*\)-\([0-9]*\).*/-(\2-\1)/ 390128785Ssmkelly x 391128785Ssmkelly s/\(.*\)\n.*/\1/ 392128785Ssmkelly x 393128785Ssmkelly b loop 394128785Ssmkelly} 395128785Ssmkelly/^\([0-9]*\)\([0-9]\)-\([0-9]*\)0=/{ 396128785Ssmkelly s//\1-\3=\2/ 397128785Ssmkelly b sub 398128785Ssmkelly} 399128785Ssmkellys/1=/0=/ 400128785Ssmkellys/2=/1=/ 401128785Ssmkellys/3=/2=/ 402128785Ssmkellys/4=/3=/ 403128785Ssmkellys/5=/4=/ 404128785Ssmkellys/6=/5=/ 405128785Ssmkellys/7=/6=/ 406128785Ssmkellys/8=/7=/ 407128785Ssmkellys/9=/8=/ 408128785Ssmkelly 409128785Ssmkellys/^\([0-9]*\)1-/\1_-/ 410128785Ssmkellys/^\([0-9]*\)2-/\11-/ 411128785Ssmkellys/^\([0-9]*\)3-/\12-/ 412128785Ssmkellys/^\([0-9]*\)4-/\13-/ 413128785Ssmkellys/^\([0-9]*\)5-/\14-/ 414128785Ssmkellys/^\([0-9]*\)6-/\15-/ 415128785Ssmkellys/^\([0-9]*\)7-/\16-/ 416128785Ssmkellys/^\([0-9]*\)8-/\17-/ 417128785Ssmkellys/^\([0-9]*\)9-/\18-/ 418128785Ssmkellys/^\([0-9]*\)0-/\1'9-/ 419128785Ssmkellys/_/0/ 420128785Ssmkelly 421128785Ssmkelly: scarry 422128785Ssmkelly/0'/{ 423128785Ssmkelly s//'9/ 424128785Ssmkelly b scarry 425128785Ssmkelly} 426128785Ssmkelly/^'/{ 427128785Ssmkelly b under 428128785Ssmkelly} 429128785Ssmkellys/1'/0/ 430128785Ssmkellys/2'/1/ 431128785Ssmkellys/3'/2/ 432128785Ssmkellys/4'/3/ 433128785Ssmkellys/5'/4/ 434128785Ssmkellys/6'/5/ 435128785Ssmkellys/7'/6/ 436128785Ssmkellys/8'/7/ 437128785Ssmkellys/9'/8/ 438128785Ssmkelly 439128785Ssmkellyb sub 440