1# This is ksb's infamous sed calculator. (ksb@sa.fedex.com) 2# 3# 4# $Id: math.sed,v 2.5 1998/08/02 13:23:34 ksb Exp ksb $ 5# expr ::= (expr) | expr! | 6# expr ^ expr | 7# -expr | expr * expr | expr / expr | expr % expr | 8# expr + expr | expr - expr | 9# [0-9][0-9]* ; 10# Bugs: some sign combinations don't work, and I got sick of added cases 11# for unary +. Don't depend on signed math working all the time. -- ksb 12# 13# $Compile: echo "4+7*3+2^7/3" | sed -f %f 14 15# make sure the expression is well formed 16s/[ ]//g 17/[*\/^%+-]$/{ 18 a\ 19 poorly formed expression, dyadic operator on the end 20 q 21} 22/^[*\/^%]/{ 23 a\ 24 poorly formed expression, leading dyadic operator 25 q 26} 27 28# fill hold space with done token 29x 30s/^.*/done/ 31x 32 33# main loop, process operators ((), !, *, /, %, +, and -) 34: loop 35# uncomment the print below to follow the "logic" -- ksb 36#p 37/^[+]/{ 38 s/// 39 b loop 40} 41/^--/{ 42 s/// 43 b loop 44} 45# eval parenthesised sub expressions first 46/^\(.*\)(\([^)]*\))\(.*\)$/{ 47 H 48 s//\2/ 49 x 50 s/^\(.*\)\n\(.*\)(\([^()]*\))\(.*\)$/()\2@\4@\1/ 51 x 52 b loop 53} 54# reduce a^b^c -> a^(b^c) 55/\([0-9][0-9]*^\)\([0-9][0-9]*^[0-9][0-9^]*\)/{ 56 s//\1(\2)/ 57 b loop 58} 59# pull any buried exponents 60/^\(.*[^0-9]\)\([0-9][0-9]*^[0-9][0-9]*\)$/{ 61 s//\1(\2)/ 62 b loop 63} 64/^\(.*[^0-9]\)\([0-9][0-9]*^[0-9][0-9]*\)\([^0-9].*\)$/{ 65 s//\1(\2)\3/ 66 b loop 67} 68/^\([0-9][0-9]*^[0-9][0-9]*\)\([^0-9].*\)$/{ 69 s//(\1)\2/ 70 b loop 71} 72/^\([-]*[0-9]*\)^0*$/{ 73 s//1/ 74 b loop 75} 76/^\([-]*[0-9]*\)^0*1$/{ 77 s//\1/ 78 b loop 79} 80/^\([-]*[0-9]*\)^-[0-9]*$/{ 81 s//0/ 82 b loop 83} 84/^\([-]*\)\([0-9]*\)^\([0-9][0-9]*[13579]\)$/{ 85 s//\1\2*((\2*\2)^(\3\/2))/ 86 b loop 87} 88/^[-]*\([0-9]*\)^\([0-9][0-9]*[02468]\)$/{ 89 s//(\1*\1)^(\2\/2)/ 90 b loop 91} 92# single digit powers (2 3,9 4,6,8 5,7 93/^[-]*\([0-9]*\)^0*2$/{ 94 s//(\1*\1)/ 95 b loop 96} 97/^\([-]*\)\([0-9]*\)^0*\([39]\)$/{ 98 s//\1(\2*(\2*\2))^(\3\/3)/ 99 b loop 100} 101/^[-]*\([0-9]*\)^0*\([468]\)$/{ 102 s//(\1*\1)^(\2\/2)/ 103 b loop 104} 105# 5 7 106/^\([-]*[0-9]*\)^\([0-9]*\)$/{ 107 s//\1*(\1^(\2-1))/ 108 b loop 109} 110# reduce all number factorials 111/^0*[01]!/{ 112 s//1/ 113 b loop 114} 115/\([*+-/%^]\)0*[01]!/{ 116 s//\11/ 117 b loop 118} 119/\([0-9]*\)!/{ 120 s//(\1-1)!*\1/ 121 b loop 122} 123# sign simplifications 124/^-\([0-9]*\)\([*/%]\)-\([0-9]*\)$/{ 125 s//\1\2\3/ 126 b loop 127} 128/^\([0-9]*\)\([*/%]\)-\([0-9]*\)$/{ 129 s//-\1\2\3/ 130 b loop 131} 132/^-\([0-9][0-9]*\)[+]*-\([0-9][0-9]*\)$/{ 133 s//\1+\2/ 134 x 135 s/\(.*\)/()-@@\1/ 136 x 137 b loop 138} 139/^-\([0-9]*\)[+]\([0-9]\)*$/{ 140 s//\2-\1/ 141 b loop 142} 143/^-.*[-+*/%].*/{ 144 H 145 s/^-// 146 x 147 s/^\(.*\)\n-.*$/()-@@\1/ 148 x 149 b loop 150} 151# can we simplify multiplications 152/^\([0-9]*\)\([*][0-9]*[1-9]\)00*$/{ 153 H 154 s//\1\2/ 155 x 156 s/^\(.*\)\n[0-9]*[*][0-9]*[1-9]\(00*\)$/()@\2@\1/ 157 x 158 b loop 159} 160/^\([0-9][1-9]*\)00*\([*][0-9]*\)$/{ 161 H 162 s//\1\2/ 163 x 164 s/^\(.*\)\n[0-9][1-9]*\(00*\)[*][0-9]*$/()@\2@\1/ 165 x 166 b loop 167} 168# can we simplify division (20/30 -> 2/3) 169/^\([0-9][0-9]*\)0\([/%]\)\([0-9][0-9]*\)0$/{ 170 s//\1\2\3/ 171 b loop 172} 173# n/1 -> n 174/^0*\([0-9][0-9]*\)0[/]0*1$/{ 175 s//\1/ 176 b loop 177} 178# n%2 -> last_digit(n)%2 (same for 1, BTW) N.B. NO LOOP 179/^[0-9]*\([0-9]\)%0*\([12]\)$/{ 180 s//\1%\2/ 181} 182# move any mul/divs to the front via parans 183/^\([0-9+]*\)\([-+]\)\([0-9]*[*/][0-9*/]*\)/{ 184 s//\1\2(\3)/ 185 b loop 186} 187# can we div or mul 188/^[0-9]*[*][0-9]*$/{ 189 b mul 190} 191/^[0-9]*[/%]0*$/{ 192 i\ 193divide by zero 194 d 195} 196/^[0-9]*[/%][0-9]*$/{ 197 H 198 s/\([0-9]\).*[/%]/\1-/ 199 x 200 s/^\(.*\)\n\([0-9]\)\([0-9]*\)\([/%]\)\([0-9]*\).*$/.\4\3q0r\2-\5@\1/ 201 x 202 b loop 203} 204/^\([0-9]*[*/%][0-9]*\)\(.*\)/{ 205 H 206 s//\1/ 207 x 208 s/^\(.*\)\n\([0-9]*[*/][0-9]*\)\(.*\)$/()@\3@\1/ 209 x 210 b loop 211} 212# can we add or subtract -- note subtract hold expression for underflow 213/^[0-9]*[+][0-9]*$/{ 214 s/$/=/ 215 b add 216} 217/^[0-9][0-9]*-[0-9]*$/{ 218 H 219 s/$/=/ 220 b sub 221} 222/^\([0-9][0-9]*[-+][0-9]*\)\(.*\)/{ 223 H 224 s//\1/ 225 x 226 s/^\(.*\)\n\([0-9]*[-+][0-9]*\)\(.*\)$/()@\3@\1/ 227 x 228 b loop 229} 230# look in hold space for stack to reduce 231x 232/^done$/{ 233 x 234 s/^0*\([0-9][0-9]*\)/\1/ 235 p 236 d 237} 238# .[/%] numerator q quotient r remainder-divisor @stack 239/^\./{ 240 x 241 /^[^-]/{ 242 H 243 x 244 s/.\(.\)\([0-9]*\)q\([^r]*\)r\([0-9]*\)-\([0-9]*\)@\(.*\)\n\(.*\)/.\1\2q\3+1r\7-\5@\6/ 245 h 246 s/..[0-9]*q[^r]*r\([0-9]*-[0-9]*\)@.*/\1/ 247 b loop 248 } 249 /^-/{ 250 g 251 /.\(.\)\([0-9]\)\([0-9]*\)q\([^r]*\)r0*\([0-9]*\)-\([^@]*\)@.*/{ 252 s//\5\2-\6/ 253 x 254 s/.\(.\)\([0-9]\)\([0-9]*\)q\([^r]*\)r0*\([0-9]*\)-\([0-9]*\)@\(.*\)/.\1\3q(\4)*10r\5\2-\6@\7/ 255 x 256 b loop 257 } 258# no digits to shift on 259 s/^\.[/]q\([^r]*\)r[^@]*@.*/\1/ 260 s/^\.[%]q[^r]*r0*\([0-9][0-9]*\)-[^@]*@.*/\1/ 261 /^\./{ 262 i\ 263divide error 264 q 265 } 266 x 267 s/^\.[/%]q[^r]*r[^@]*@\(.*\)/\1/ 268 x 269 b loop 270 } 271} 272/^()/{ 273 s/// 274 x 275 G 276 s/\(.*\)\n\([^@]*\)@\([^@]*\)@\(.*\)/\2\1\3/ 277 x 278 s/[^@]*@[^@]*@\(.*\)/\1/ 279 x 280 b loop 281} 282i\ 283help, stack problem - the hold space 284p 285x 286i\ 287and the pat space 288p 289i\ 290quit 291q 292 293# turn mul into add until 1*x -> x, 0*x -> 0 294: mul 295/^00*\*.*/{ 296 s//0/ 297 b loop 298} 299/^0*1\*/{ 300 s/// 301: leading 302 s/^0*\([0-9][0-9]*\)/\1/ 303 b loop 304} 305s/^\([0-9]*\)0\*\([0-9]*\)/\1*\20/ 306s/^\([0-9]*\)1\*\([0-9]*\)/\1*\20+\2/ 307s/^\([0-9]*\)2\*\([0-9]*\)/\1*\20+(\2+\2)/ 308s/^\([0-9]*\)3\*\([0-9]*\)/\1*\20+(\2+\2+\2)/ 309s/^\([0-9]*\)4\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2)/ 310s/^\([0-9]*\)5\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2)/ 311s/^\([0-9]*\)6\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2)/ 312s/^\([0-9]*\)7\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2)/ 313s/^\([0-9]*\)8\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2+\2)/ 314s/^\([0-9]*\)9\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2+\2+\2)/ 315/^0*\*[0-9]*[+]*\(.*\)/{ 316 s//\1/ 317 b loop 318} 319b mul 320 321# get rid of a plus term until 0+x -> x 322: add 323/^[+]\([0-9+*]*\)=/{ 324 s//\1/ 325 b leading 326} 327/^\([0-9*]*\)[+]=/{ 328 s//\1/ 329 b loop 330} 331/^\([0-9]*\)0[+]\([0-9]*\)\([0-9]\)=/{ 332 s//\1+\2=\3/ 333 b add 334} 335/^\([0-9]*\)\([0-9]\)[+]\([0-9]*\)0=/{ 336 s//\1+\3=\2/ 337 b add 338} 339s/^\([0-9]*\)1[+]/\10+/ 340s/^\([0-9]*\)2[+]/\11+/ 341s/^\([0-9]*\)3[+]/\12+/ 342s/^\([0-9]*\)4[+]/\13+/ 343s/^\([0-9]*\)5[+]/\14+/ 344s/^\([0-9]*\)6[+]/\15+/ 345s/^\([0-9]*\)7[+]/\16+/ 346s/^\([0-9]*\)8[+]/\17+/ 347s/^\([0-9]*\)9[+]/\18+/ 348 349s/9=\([0-9]*\)$/_=\1/ 350s/8=\([0-9]*\)$/9=\1/ 351s/7=\([0-9]*\)$/8=\1/ 352s/6=\([0-9]*\)$/7=\1/ 353s/5=\([0-9]*\)$/6=\1/ 354s/4=\([0-9]*\)$/5=\1/ 355s/3=\([0-9]*\)$/4=\1/ 356s/2=\([0-9]*\)$/3=\1/ 357s/1=\([0-9]*\)$/2=\1/ 358/_/{ 359 s//_0/ 360 : inc 361 s/9_/_0/ 362 s/8_/9/ 363 s/7_/8/ 364 s/6_/7/ 365 s/5_/6/ 366 s/4_/5/ 367 s/3_/4/ 368 s/2_/3/ 369 s/1_/2/ 370 s/0_/1/ 371 s/[+]_/+1/ 372 /_/b inc 373} 374b add 375 376# get rid of a sub term until /-0*=/ or underflow 377: sub 378/^\([0-9]*\)-0*=/{ 379 s//\1/ 380 x 381 s/\(.*\)\n.*$/\1/ 382 x 383 b leading 384} 385/^-\([0-9].*\)=/{ 386: under 387 g 388 s/.*\n\([0-9]*\)-\([0-9]*\).*/-(\2-\1)/ 389 x 390 s/\(.*\)\n.*/\1/ 391 x 392 b loop 393} 394/^\([0-9]*\)\([0-9]\)-\([0-9]*\)0=/{ 395 s//\1-\3=\2/ 396 b sub 397} 398s/1=/0=/ 399s/2=/1=/ 400s/3=/2=/ 401s/4=/3=/ 402s/5=/4=/ 403s/6=/5=/ 404s/7=/6=/ 405s/8=/7=/ 406s/9=/8=/ 407 408s/^\([0-9]*\)1-/\1_-/ 409s/^\([0-9]*\)2-/\11-/ 410s/^\([0-9]*\)3-/\12-/ 411s/^\([0-9]*\)4-/\13-/ 412s/^\([0-9]*\)5-/\14-/ 413s/^\([0-9]*\)6-/\15-/ 414s/^\([0-9]*\)7-/\16-/ 415s/^\([0-9]*\)8-/\17-/ 416s/^\([0-9]*\)9-/\18-/ 417s/^\([0-9]*\)0-/\1'9-/ 418s/_/0/ 419 420: scarry 421/0'/{ 422 s//'9/ 423 b scarry 424} 425/^'/{ 426 b under 427} 428s/1'/0/ 429s/2'/1/ 430s/3'/2/ 431s/4'/3/ 432s/5'/4/ 433s/6'/5/ 434s/7'/6/ 435s/8'/7/ 436s/9'/8/ 437 438b sub 439