usr.bin/sed/tests/math.sed

   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
  16 s/[     ]//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
  29 x
  30 s/^.*/done/
  31 x
  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\
 193 divide 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
 231 x
 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\
 263 divide 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 }
 282 i\
 283 help, stack problem - the hold space
 284 p
 285 x
 286 i\
 287 and the pat space
 288 p
 289 i\
 290 quit
 291 q
 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 }
 305 s/^\([0-9]*\)0\*\([0-9]*\)/\1*\20/
 306 s/^\([0-9]*\)1\*\([0-9]*\)/\1*\20+\2/
 307 s/^\([0-9]*\)2\*\([0-9]*\)/\1*\20+(\2+\2)/
 308 s/^\([0-9]*\)3\*\([0-9]*\)/\1*\20+(\2+\2+\2)/
 309 s/^\([0-9]*\)4\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2)/
 310 s/^\([0-9]*\)5\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2)/
 311 s/^\([0-9]*\)6\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2)/
 312 s/^\([0-9]*\)7\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2)/
 313 s/^\([0-9]*\)8\*\([0-9]*\)/\1*\20+(\2+\2+\2+\2+\2+\2+\2+\2)/
 314 s/^\([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 }
 319 b 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 }
 339 s/^\([0-9]*\)1[+]/\10+/
 340 s/^\([0-9]*\)2[+]/\11+/
 341 s/^\([0-9]*\)3[+]/\12+/
 342 s/^\([0-9]*\)4[+]/\13+/
 343 s/^\([0-9]*\)5[+]/\14+/
 344 s/^\([0-9]*\)6[+]/\15+/
 345 s/^\([0-9]*\)7[+]/\16+/
 346 s/^\([0-9]*\)8[+]/\17+/
 347 s/^\([0-9]*\)9[+]/\18+/
 348
 349 s/9=\([0-9]*\)$/_=\1/
 350 s/8=\([0-9]*\)$/9=\1/
 351 s/7=\([0-9]*\)$/8=\1/
 352 s/6=\([0-9]*\)$/7=\1/
 353 s/5=\([0-9]*\)$/6=\1/
 354 s/4=\([0-9]*\)$/5=\1/
 355 s/3=\([0-9]*\)$/4=\1/
 356 s/2=\([0-9]*\)$/3=\1/
 357 s/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 }
 374 b 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 }
 398 s/1=/0=/
 399 s/2=/1=/
 400 s/3=/2=/
 401 s/4=/3=/
 402 s/5=/4=/
 403 s/6=/5=/
 404 s/7=/6=/
 405 s/8=/7=/
 406 s/9=/8=/
 407
 408 s/^\([0-9]*\)1-/\1_-/
 409 s/^\([0-9]*\)2-/\11-/
 410 s/^\([0-9]*\)3-/\12-/
 411 s/^\([0-9]*\)4-/\13-/
 412 s/^\([0-9]*\)5-/\14-/
 413 s/^\([0-9]*\)6-/\15-/
 414 s/^\([0-9]*\)7-/\16-/
 415 s/^\([0-9]*\)8-/\17-/
 416 s/^\([0-9]*\)9-/\18-/
 417 s/^\([0-9]*\)0-/\1'9-/
 418 s/_/0/
 419
 420 : scarry
 421 /0'/{
 422         s//'9/
 423         b scarry
 424 }
 425 /^'/{
 426         b under
 427 }
 428 s/1'/0/
 429 s/2'/1/
 430 s/3'/2/
 431 s/4'/3/
 432 s/5'/4/
 433 s/6'/5/
 434 s/7'/6/
 435 s/8'/7/
 436 s/9'/8/
 437
 438 b sub