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