# 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. Jul 9, 2017 at 0:38
• Three of the 'six' are identical, as are another two. That leaves three actual cases, not six. Jul 9, 2017 at 12:13
• how % operator works on negative numbers? The way like C or Python or something else?
– tsh
Jul 9, 2017 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. :) Jul 9, 2017 at 16:57
• @tsh Any behavior. Do whatever you want. You can make demons fly out of my nose. Jul 10, 2017 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)]],[]) Jul 9, 2017 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. Jul 9, 2017 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! Jul 10, 2017 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. Jul 10, 2017 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),). Jul 9, 2017 at 1:11 • Huh, TIL. Thanks for the tip! Jul 9, 2017 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! Jul 9, 2017 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?")")
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)=... Jul 10, 2017 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. Jul 10, 2017 at 13:46 • Also I am counting 594 bytes, not 582. Jul 10, 2017 at 13:48 # 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. Jul 10, 2017 at 13:57 # 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, 2017 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? Jul 10, 2017 at 11:45 • @trlkly a/b|0 stops the divide/modulo 0 error check, but Math.floor(a/b) worked Jul 10, 2017 at 12:43 # 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! Jul 9, 2017 at 2:12 • Save one byte by changing in [ to in[ (space isn't needed) Jul 9, 2017 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 Jul 10, 2017 at 0:28

# 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>

# 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. Jul 9, 2017 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. Jul 10, 2017 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/… Jul 10, 2017 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. Jul 10, 2017 at 9:05
• @Challenger5 So I need to add 41 bytes into my bytecount, right? OK. Jul 10, 2017 at 10:15
• @Qwerp-Derp Yes, but the import is part of your code, and you can golf it. Jul 11, 2017 at 2:13