# Operator precedence: How wrong can I be?

Say I have an expression:

9 * 8 + 1 - 4


This expression can be interpreted in six different ways, depending on operator precedence:

(((9 * 8) + 1) - 4) = 69 (* + -)
((9 * 8) + (1 - 4)) = 69 (* - +)
((9 * (8 + 1)) - 4) = 77 (+ * -)
(9 * ((8 + 1) - 4)) = 45 (+ - *)
((9 * 8) + (1 - 4)) = 69 (- * +)
(9 * (8 + (1 - 4))) = 45 (- + *)


Say I'm a developer, and I don't feel like memorizing precedence tables, etc., so I'm just going to guess.

In this case, the largest margin of error would be 45-77, which is a difference of 32. This means that my guess will only be off by a maximum of 32.

## The challenge

Given an expression consisting of numbers and +, -, *, / (integer division) and %, output the absolute difference of the largest and smallest possible value for that expression, based on the precedence of operators.

## Specifications

• The input expression will not contain parenthesis and every operator is left-associative.
• The input expression will only contain nonnegative integers. However, subexpressions may evaluate to negatives (e.g. 1 - 4).
• You can take the expression in any reasonable format. For example:
• "9 * 8 + 1 - 4"
• "9*8+1-4"
• [9, "*", 8, "+", 1, "-", 4]
• [9, 8, 1, 4], ["*", "+", "-"]
• The input will contain at least 1 and at most 10 operators.
• Any expression that contains a division or modulo by 0 should be ignored.
• You can assume that modulo will not be given negative operands.

## Test Cases

9 * 8 + 1 - 4             32
1 + 3 * 4                  3
1 + 1                      0
8 - 6 + 1 * 0              8
60 / 8 % 8 * 6 % 4 * 5    63

• @AndersKaseorg It looks like you're treating % as having two different precedences in your second example. – Esolanging Fruit Jul 9 '17 at 0:38
• Three of the 'six' are identical, as are another two. That leaves three actual cases, not six. – user207421 Jul 9 '17 at 12:13
• how % operator works on negative numbers? The way like C or Python or something else? – tsh Jul 9 '17 at 14:33
• Just saying, you don't have to add the "and I'm lazy" part to your description. Just saying you're a developer is enough. :) – Gryphon Jul 9 '17 at 16:57
• @tsh Any behavior. Do whatever you want. You can make demons fly out of my nose. – Esolanging Fruit Jul 10 '17 at 7:11

# Python 2, 171 156 bytes

lambda a:max(e(a))-min(e(a))
u=')%s('
def e(a,t=u):
try:b=[eval(a)]
except:b=[]
return sum([e('(%s)'%a.replace(o,t%o),u%t)for o in"+-*/%"if' '+o in a],b)


Try it online!

### How it works

We surround each operator with a different number of outward-facing pairs of parentheses to simulate different precedences (in all possible ways), and wrap enough inward-facing pairs of parentheses around the entire string, to get an expression we can eval. For example, with

+)+(
*))*((
-)))-(((

we get

9 * 8 + 1 - 4(((9 ))*(( 8 )+( 1 )))-((( 4))) = 77.

• You can save 2 bytes by moving the or outside the sum to remove a layer of square brackets: sum([...],[])or[eval(a)] instead of sum([...]or[[eval(a)]],[]) – Strigoides Jul 9 '17 at 6:29
• @Strigoides I had been thinking that wasn’t equivalent, because the sum may be empty without its argument being empty—however, it’s actually fine because the eval must fail in that case. Thanks. – Anders Kaseorg Jul 9 '17 at 7:24

# Jelly, 126 bytes

"Operator Precedence? Parentheses? Pah, who needs that?" - challenges of using Jelly for an operator precedence challenge.

⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€ ÇµḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/ ÇµVṾµ1ĿFḟØDḟ”-Lµ?ÐL 5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ “+_×:%”Œ!Ç€µṾL_L’ỊµÐfV€ṢIS  Try it online! Input is taken as a string, e.g. "1+2_3×4:5%6". Note multiplication uses "×" instead of "*", division uses ":" instead of "/", and subtraction uses "_" instead of "-". How it Works The program is divided into three parts: generating all expressions of different operator precedence, evaluating them, and returning the difference between the maximum and minimum. All expressions are generated with the code: 5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ (4) helper link: returns all outputs given a permutation. Input e.g. "_+:×%" 5Ḷx@€“]“[” - repeat outer brackets to get ["",""],["]","["],["]]","[["],["]]]","[[["],["]]]]","[[[["] ż⁸j/€ - insert the operations in to get "_","]+[","]]:[[","]]]×[[[","]]]]%[[[[" ,@ - turn this into a mapping equivalent to "_"↦"_","+"↦"]+[",":"↦"]]:[[","×"↦"]]]×[[[","%"↦"]]]]%[[[[" y³F - use this mapping to get the right number of outward brackets on each operation. e.g. "1]+]]×[[[4" ɓ³i@€Ṁ’x@“[“]”j - add the right number of brackets to the end to get e.g."[[+]]×[[]]" Ç - this calls the link which evaluates the expression “+_×:%”Œ!Ç€ (5a) main link. Input e.g. "1+3×4" “+_×:%” - the string "+_×:%" Œ! - all permutations Ç€ - apply link (4) to each permutation  The links are evaluated with this (I could probably improve with a different structure): ⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€      (1) Helper link: Outputs a list of expressions within brackets, e.g. "[[+]]×[[]]"↦"[+]","[]"
⁾[]i$€Ḥæ%3 - map "[" to 2, "]" to -2, and any other character to 0. +\¬ - cumulative sum negated: 1s at characters not in brackets (includes opening brackets), 0s otherwise (includes closing brackets) œp¹ - partition the input, not including borders, based on the sum to get "[[+]","[[]" Ḋ€ - remove opening brackets ÇµḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/ (2) Return the input to this link with one of the expressions from (1) evaluated ÇµVṾµ1ĿFḟØDḟ”-Lµ?ÐL (3) link called from part 1: Evaluates expressions µ µ µ? - if: 1ĿFḟØDḟ”-L - the input contains no operators within brackets: VṾ - evaluate this one expression with normal Jelly calculation and return to string - otherwise: Ç - evaluate one subexpression using link (2) ÐL - repeat this until a single output is determined  The difference between the maximum and minimum is computed with the code in link (5): µṾL_L’ỊµÐfV€ṢIS (5b) determine difference between minimum and maximum µ µÐf - filter out outputs involving division or modulo by 0. Determined with: ṾL_L’Ị - actual numbers have their unevaled form Ṿ no more than one byte longer than the non-unevaled form. V€ - evaluate each of these valid numbers to get integers from strings Ṣ - sort IS - return the sum of all difference between consecutive elements.  • Probably the longest Jelly answer (without embedded data) I've ever seen. Well done! – Keyu Gan Jul 10 '17 at 1:51 • @KeyuGan If you want longer Jelly answers, look at this answer. I can't think of any other long Jelly answers without compression. – fireflame241 Jul 10 '17 at 1:57 # Python 2, 235234233 226 bytes -1 byte (and a fix) thanks to Anders Kaseorg! -7 bytes thanks to Step Hen! from itertools import* def f(e,a=()): for o in permutations("+-*/%"): l=e[:] for c in o: for i in range(len(l),0,-1): if l[i-1]==c:l[i-2:i+1]=["("+l[i-2]+l[i-1]+l[i]+")"] try:a+=eval(*l), except:0 print max(a)-min(a)  Try it online! • Function submissions must be reusable. You can fix that problem by letting a be a tuple instead of a list, and even save 1 byte by doing so (a=(), a+=eval(*l),). – Anders Kaseorg Jul 9 '17 at 1:11 • Huh, TIL. Thanks for the tip! – notjagan Jul 9 '17 at 1:14 • Since you're in Python 2, you can save some bytes by alternating spaces and tabs for indentation (in this case, 2 spaces -> tab, three spaces -> tab + space, four spaces -> two tabs) Try it online! – Stephen Jul 9 '17 at 2:11 # Haskell 582 bytes This didn't go nearly as well as I hoped it would... import Data.List f x=case x of '+'->(+);'-'->(-);'*'->(*);'/'->div;_->rem e _ s[]=s e 1 s(')':x:a)|0<-(read$e 0""a),(x=='%'||x=='/')=""|""<-(e 0""s)=""|""<-(e 0""a)=""|0<3=show$(f x)(read$e 0""s)$read$e 0""a
e 1 s")"=e 0""s
e n s(')':a)=e(n-1)(s++")")a
e 0 s('(':a)=e 1 s a
e n s('(':a)=e(n+1)(s++"(")a
e n s(x:a)=e n(s++[x])a
n?s=take n$cycle s a!b=e 0""(9?"("++(concat$zipWith(++)a(b++[[]]))++9?")")
c#b|l<-[read x|x<-map(c!)(a b),x/=""]=maximum l-minimum l
a c=transpose$map(\x->map((\(Just q)->q).lookup x)$map(\a->zipWith(\x y->(y,x?")"++y:x?"("))[1..5]a)$permutations"+-*%/")c  Try It Online! Trying to golf a long program just makes me write bad code :( I tried to use Anders' algorithm in Haskell, but it got out of my control The function e is like a specific case of eval. (#) takes a list of strings representing integers and a string of operators and returns the difference between the maximum and minimum possible values. e.g (#) ["9","8","1","4"] "*+-" => 32  • If you renamed # to ##, you could rename e to (#), like so: (n#s)(x:a)=... – Esolanging Fruit Jul 10 '17 at 9:13 • If you alias the following three commonly used functions you can save a further 6 bytes. r=read;j=zipWith;o=map and then replace those functions with the letter aliases. – maple_shaft Jul 10 '17 at 13:46 • Also I am counting 594 bytes, not 582. – maple_shaft Jul 10 '17 at 13:48 # Pyth, 45 bytes KS.nm.x.vj\ u.nm+*H/kHckHGd]s.iFQY.p_{eQ-eKhK  I'm sure that a lot more optimization can be done, but I like it so far. Takes input like this: [9, 8, 1, 4], ["*", "+", "-"]. Try it online! • Can you add an explanation? – Jim Jul 10 '17 at 16:14 # Mathematica, 186164 159 bytes eMax@#-Min@#&[Fold[#//.{m___,x_,#2[],y_,n___}:>{m,x~Last@#2~y,n}&,e,#]&/@Permutations@{"+"@Plus,"-"[#-#2&],"*"@Times,"/"@Quotient,"%"@Mod}/. 0/0|1/0->{}]  \[Function] takes 3 bytes. Some alternatives (keeps bytecount the same) #2-#&@MinMax[...] to replace Max@#-Min@#&[...] Head@#2 to replace #2[] Try it online at http://sandbox.open.wolframcloud.com : enter ( .... )[{60, "/", 8, "%", 8, "*", 6, "%", 4, "*", 5}] with .... replaced by code above for test case 60 / 8 % 8 * 6 % 4 * 5. Press Shift + enter to evaluate. # Javascript, 280 bytes Note: The integer division rounds using the floor function, which means that negative numbers round away from zero. This solution is based on this answer. b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval((${a})[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b)))


Example code snippet:

g=

b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval((${a})[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b))) for(k=0;k<5;k++) v=["9*8+1-4","1+3*4","1+1","8-6+1*0","60/8%8*6%4*5"][k], console.log(g(${v}) = ${g(v)}) • How hard would it be to make it compliant by replacing the a/b case with a/b|0? – trlkly Jul 10 '17 at 11:45 • @trlkly a/b|0 stops the divide/modulo 0 error check, but Math.floor(a/b) worked – Herman L Jul 10 '17 at 12:43 # Haskell, 254 bytes import Data.List.Split import Data.List f s=(-)<$>maximum<*>minimum$permutations(zip"+-*/%"[p(+),p(-),p(*),c$div,c$mod])>>=(s!) p=((pure.).) c o a b=[o a b|b/=0] s![]=[read s] s!((x,o):y)=case splitOn[x]s>>=(!y)of[]->[];l->l?o [a]?_=[a] (a:b)?o=b?o>>=o a  Try it online! Input is a whole string, such as 4+5 * 2. It generates all permutations of operations, and for each permutation splits the string recursively. It filters divisions by 0 with the list monad. • (%) is modulus operator. It is remainder of a division operation between the left argument and the right argument. – maple_shaft Jul 10 '17 at 13:57 # Python 2, 262256 254 bytes from itertools import* def r(s,o): try: while o in s:i=s.index(o)-1;s[i:i+3]=[eval(''.join(s[i:i+3]))] return s except:0 def f(s): u=[int(v)for v in [reduce(r,O,s.split(' '))for O in permutations('*/%+-')]if v!=None];return abs(max(u)-min(u))  Try it online! • Save some bytes by also using tabs: Try it online! – Stephen Jul 9 '17 at 2:12 • Save one byte by changing in [ to in[ (space isn't needed) – Zacharý Jul 9 '17 at 15:12 # PHP, 316 bytes <?for(;$t++<54322;)count_chars($t,3)!=12345?:$p[]=$t;foreach($p as$x){for(list($z,$q)=$_GET,$b=1,$i=0;$y=strtr($x,12345,"/%*+-")[$i++];)while(-1<$k=array_flip($q)[$y]){$n=$k+1;if($b&=$z[$n]||ord($y)%10<6)eval("$z[k]=z[k]yz[n]^0;");(s=array_splice)(z,n,1);s(q,k,1);}b?r[]=z:0;}echo max(r)-min(r);  Try it online! Expanded for(;t++<54322;) count_chars(t,3)!=12345?:p[]=t; foreach(p asx){ for(list(z,q)=_GET,b=1,i=0;y=strtr(x,12345,"/%*+-")[i++];) while(-1<k=array_flip(q)[y]){ n=k+1; if(b&=z[n]||ord(y)%10<6) eval("$z[$k]=$z[$k]$y$z[$n]^0;");
($s=array_splice)($z,$n,1);$s($q,$k,1);
}
$b?$r[]=$z:0; } echo max($r)-min(\$r);

• The lase case is 63. Your mistake due to giving the same operator a different precedence in different parts of one expression – H.PWiz Jul 10 '17 at 0:28

# Python 3, 284 bytes

Edit: seems like something's wrong with evaluating the last example. I'll look into it tomorrow.

Another Python answer. Couldn't outgolf everyone else, but I spent too long on this to not put it up.

from itertools import*
def f(n,o):
z=[]
for p in permutations("+-*/%"):
try:
p,x,a=[*p],n[:],o[:]
while(p):
for i,d in enumerate(a):
if d==p:x[i+1]=str(eval(x[i]+d+x[i+1]));x.pop(i);a.pop(i)
p.pop(0)
z+=x
except:0
z=[*map(float,z)];return max(z)-min(z)


Try it online!

• while(p) can become while p for one byte saved. – Zacharý Jul 9 '17 at 15:10

# Clojure (+ combinatorics), 342 377 + 41 = 418 bytes

+35 bytes because of a bug.

(fn[x y](let[l filter s first z #(l(fn[y]y)%)r(sort(z(for[e(q/permutations[+ - * quot mod])](try(loop[t e m y a x](if(=[]t)(s a)(let[j(s t)i(reverse(keep-indexed #(if(= j %2)%)m))](recur(rest t)(l #(not= j %)m)(loop[d 0 h a](if(=(count i)d)h(let[c(nth i d)f(inc c)](recur(inc d)(vec(z(assoc h c(j(nth h c)(nth h f))f nil)))))))))))(catch Exception _ nil)))))](-(last r)(s r))))


Try it online!

For this function to work, you have to use the clojure.math.combinatorics library (41 bytes):

(use '[clojure.math.combinatorics :as q])


## Nuances:

This function is an anonymous function, which means you must do this to use it:

((fn[x y]...) numbers operators)


Also, I'm using the word quot instead of / (since Clojure does fraction division by default), and mod instead of %.

## Ungolfed program:

(defn precedence [numbers operators]
(let [results
(sort
(for [permute (c/permutations [+ - * / mod])]
(loop [p-temp permute
o-temp operators
n-temp numbers]
(if (empty? o-temp) (first n-temp)
(let [first-p (first p-temp)
indices (reverse (keep-indexed #(when (= first-p %2) %) o-temp))]
(recur
(rest p-temp)
(filter #(not= first-p %) o-temp)
(loop [ind 0
n-through n-temp]
(if (= ind (count indices)) n-through
(let [current-ind (nth indices ind)]
(recur
(inc ind)
(vec
(filter #(not (nil? %))
(assoc n-through
current-ind (first-p (nth n-through current-ind) (nth n-through (inc current-ind)))
(inc current-ind) nil)))))))))))))]
(- (last results) (first results))))

• I think you can just say "Closure + Combinatorics" and not have to score the use statement. – Esolanging Fruit Jul 10 '17 at 5:04
• @Challenger5 I believe you'd better write it in the description, because by default, The characters used to import the library will likely be counted codegolf.meta.stackexchange.com/questions/10225/… – Keyu Gan Jul 10 '17 at 8:20
• @KeyuGan You're right - I misunderstood that Meta consensus. I think the require needs to be included in the code and its length should be added to the byte count. – Esolanging Fruit Jul 10 '17 at 9:05
• @Challenger5 So I need to add 41 bytes into my bytecount, right? OK. – Qwerp-Derp Jul 10 '17 at 10:15
• @Qwerp-Derp Yes, but the import is part of your code, and you can golf it. – Esolanging Fruit Jul 11 '17 at 2:13

# JavaScript (ES6), 210 bytes

Input as an array of numbers and operators

k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n


Less golfed

k=>(
m = n = NaN,
r =(o, k, j=0) => {
// try all operators in o
for(;q = o[j]; j++)
{
// q : current operator,
// look for q inside the expression to evaluate
for(h = [...k], z = 1; i = h.indexOf(q) + 1;)
{
a = h[i - 2]
b = h[i]
z *= b // trace if any second operand is zero
// subst subexpression with its value
h.splice(i - 2, 3, eval(a + q + b) | 0)
}
// now all subexp involving current operator are evaluated
// the result is ok if current operator is not % or /
//  OR if no second operand was zero
(q > '%' & q < '/' || z) &&
// try again recursively
// using the remaining operators and the remaining expression
r(o.slice(0, j) + o.slice(j+1), h)
}
// if no more operators to try, check max and min
// k is an array with 1 element, can be used like a single number
o || (
m = m > k ? m : k,
n = n < k ? n : k
)
},
r('+-*/%', k),
m-n
)


Test

var F=
k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n

function update() {
var input = I.value.match(/\d+|\S/g)
var result = F(input)
O.textContent = I.value + ' -> ' + result + ' (max:'+m+' min:'+n+')'
}

update()
<input id=I value="60 / 8 % 8 * 6 % 4 * 5" oninput='update()'>
<pre id=O></pre>