tools/regression/usr.bin/sed/math.sed

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