# Preamble

Integers are always either even or odd. Even integers are divisible by two, odd integers are not.

When you add two integers you can infer whether the result will be even or odd based on whether the summands were even or odd:

• Even + Even = Even
• Even + Odd = Odd
• Odd + Even = Odd
• Odd + Odd = Even

Likewise, when you multiply two integers you can infer whether the result will be even or odd based on whether the factors were even or odd:

• Even * Even = Even
• Even * Odd = Even
• Odd * Even = Even
• Odd * Odd = Odd

Thus, if you know the evenness or oddness of all the variables in a math expression that only involves addition and multiplication, you can infer whether the result will be even or odd.

For example, we can confidently say that (68 + 99) * 37 results in an odd because an even plus an odd (68 + 99) is an odd, and that odd times another odd (odd * 37) gives an odd.

# Challenge

Write a program or function that takes in a string only containing the four characters eo+*. This string represents a mathematical expression given in prefix notation involving only addition (+) and multiplication (*). Each e represents some arbitrary even number, and each o represents some arbitrary odd number.

Your task is to simplify the expression, printing or returning a single e or o based on whether the result of the expression is even or odd.

You can assume that the input will always be in valid prefix notation. Specifically, each + and * will always have two corresponding operands occurring after it. These operands may be a single e or o, or another + or * expression that in turn has operands.

For example, the input *+eoo could be read as mul(add(e, o), o), or (e + o) * o in normal infix notation. The e and the first o are the operands corresponding to the +, and +eo and the last o are the operands corresponding to the *.

Just to make it clear, here are some invalid inputs that have incorrect prefix notation:

eo
ooe
o+e
ee*
+*oe
+e*o


A single trailing newline in the output is fine, but otherwise a plain e for even or o for odd is all that should be output.

The shortest code in bytes wins.

# Test Cases

(Empty lines are only to help visually separate similar cases.)

e -> e
o -> o

+ee -> e
+eo -> o
+oe -> o
+oo -> e
*ee -> e
*eo -> e
*oe -> e
*oo -> o

+e+ee -> e
+e+eo -> o
+e+oe -> o
+e+oo -> e
+e*ee -> e
+e*eo -> e
+e*oe -> e
+e*oo -> o

+o+ee -> o
+o+eo -> e
+o+oe -> e
+o+oo -> o
+o*ee -> o
+o*eo -> o
+o*oe -> o
+o*oo -> e

*e+ee -> e
*e+eo -> e
*e+oe -> e
*e+oo -> e
*e*ee -> e
*e*eo -> e
*e*oe -> e
*e*oo -> e

*o+ee -> e
*o+eo -> o
*o+oe -> o
*o+oo -> e
*o*ee -> e
*o*eo -> e
*o*oe -> e
*o*oo -> o

++eee -> e
++eeo -> o
++eoe -> o
++eoo -> e
++oee -> o
++oeo -> e
++ooe -> e
++ooo -> o

+*eee -> e
+*eeo -> o
+*eoe -> e
+*eoo -> o
+*oee -> e
+*oeo -> o
+*ooe -> o
+*ooo -> e

*+eee -> e
*+eeo -> e
*+eoe -> e
*+eoo -> o
*+oee -> e
*+oeo -> o
*+ooe -> e
*+ooo -> e

**eee -> e
**eeo -> e
**eoe -> e
**eoo -> e
**oee -> e
**oeo -> e
**ooe -> e
**ooo -> o

+e+e+e+ee -> e
+o+o+o+oo -> o
*e*e*e*ee -> e
*o*o*o*oo -> o
+e+o+e+oe -> e
+o+e+o+eo -> o
*e*o*e*oe -> e
*o*e*o*eo -> e
+e*e+e*ee -> e
+o*o+o*oo -> o
*e+e*e+ee -> e
*o+o*o+oo -> o

+**++*+*eeoeeooee -> e
+**++*+***eooeoeooeoe -> e
+**+***+**++**+eooeoeeoeeoeooeo -> o

+e*o*e**eoe -> e
+*e+e+o+e**eeoe -> e
**o++*ee*++eoe*eo+eoo -> o
• Can we take 1 and 0 instead of e and o as input? Dec 2 '15 at 10:30
• @ghosts_in_the_code No, sorry. Dec 2 '15 at 10:32
• Is using eval OK?
– xnor
Dec 2 '15 at 10:45
• @xnor Sure. Whatever works. Dec 2 '15 at 10:47
• I doubt I can use this to beat the 13 bytes already posted, but I notice that addition matches an exclusive or and multiplication a simple or. Dec 3 '15 at 16:19

## CJam, 1817 13 bytes

Thanks to aditsu for saving 4 bytes.

qW:O%eu~"eo"=


Try the test suite here. (The test suite is too long for the permalink. Just copy them from the challenge spec.)

### Explanation

q     e# Read the input.
W:O   e# Push a -1 and store it in variable O.
%     e# Use the -1 to reverse the string, because CJam's stack-based nature and the
e# commutativity of the operators means we can evaluate the code in postfix notation.
eu    e# Convert the string to upper case, turning 'e' into 'E' (a variable with even value
e# 14) and 'o' into 'O' (which we've stored the odd value -1 in).
~     e# Evaluate the string as CJam code, leaving the result on the stack.
"eo"= e# Use the result as an index into the string "eo". CJam's indexing is cyclic so it
e# automatically takes inputs modulo 2. Negative indices also work as expected.


# Pyth, 16 14 bytes

@"eo".vjdXzGU9


Pyth can itself evaluate a string, that is in Pyth syntax. Therefore I replace e and o with 4 and 5. Then the evaluation will give me an even or odd number, and I can easily print the result.

Try it online: Demonstration or Test Suite

### Explanation:

@"eo".vjdXzGU9   implicit: z = input string
XzGU9   replace "e" in z with 4 and "o" with 5
jd        put a space between each char
.v          evaluate it (Pyth style)
@"eo"            and print "e" or "o"


Additional explanation to the replace. G is a variable initialized with the alphabet abc...xyz. U9 is the list [0, 1, ..., 8]. XzGU9 replaces the letters of the alphabet with the values of the list. So a gets replaced with 0, b with 1, ..., e with 4, ..., i with 8, j with 0, ..., and o with 5. Therefore I e gets replaced with an even number and o with an odd number. All the other replacements have no effect at all.

• Why are you reversing the expression? Also, don't you need to take the result modulo 2, or is the indexing wrapping around?
– xnor
Dec 2 '15 at 10:50
• @xnor accessing an element in a string is done modulo wrapping. So no need for modulo 2. Dec 2 '15 at 11:26
• @xnor But thanks for the reverse thing. Of course this is not necessary. (I'm a litle bit tired today.) Dec 2 '15 at 11:27

# Perl, 5045 40 characters

(39 characters code + 1 character command line option.)

1while s/\+oe|\+eo|\*oo/o/||s/\W\w\w/e/


Sample run:

bash-4.3$echo -n '**o++*ee*++eoe*eo+eoo' | perl -pe '1while s/\+oe|\+eo|\*oo/o/||s/\W\w\w/e/' o  • How about while/../? Dec 2 '15 at 11:21 • Doh. Me stupid. Actually used that condition while tried its sed version… Thank you, @primo. Dec 2 '15 at 11:22 • Or even better, 1while s/\+oe.... I'm also pretty sure [+*] can be replaced with \W. Dec 2 '15 at 11:31 • Thank you again, @primo. I think I should concentrate on a single solution once. (gema driving me mad…) Dec 2 '15 at 11:36 • Same approach with Sed now 2 bytes shorter! Dec 4 '15 at 22:40 # Python 2, 90 def f(s):i=iter(s);a=next(i);return(a>'a')*a or'oe'[f(i)==f(i)if'*'<a else'e'in f(i)+f(i)]  The iter function is a good way to make the input string into a FIFO queue which remembers how much of the string has been parsed across calls of f. It is idempotent, so it is harmless to call it again when the input is already an iterator rather than a string. The trailing half of the answer beginning with or'oe'... seems like it should be golfable, but I couldn't find anything. -1 thanks to Sp3000. • Great solution! Recursive functions using iter really boggle my mind. – xnor Dec 2 '15 at 20:55 • Here's a way to compute the arithmetic directly with eval: def f(s,e=0,o=1):i=iter(s);a=next(i);return'eo'[eval(a*(a>'a')or f(i)+a+f(i))%2] – xnor Dec 2 '15 at 21:08 • @xnor You might as well post that as an answer. It is much different from this solution. Dec 3 '15 at 0:04 # Retina, 29 bytes (+\*oo|\+(eo|oe) o \W\w\w e  For the convenient one file version the -s flag is used. We swap odd expressions (*oo, +oe, +eo) to o until we can, then swap the remaining symbol-letter-letter expressions to e. We repeat this until we can and the final one letter is our output. (This solution is similar to manatwork's Perl answer.) Try it online! (by Dennis) ## Python 2, 80 bytes def f(s,e=0,o=1):i=iter(s);a=next(i);return(a>'a')*a or'eo'[eval(f(i)+a+f(i))%2]  This is built on feersum's very clever answer that uses an iter to implement Polish-notation operations. The new idea is to use eval to evaluate the expressions + and * with eval(f(i)+a+f(i)), where the operator a is placed infix between the recursive results. The eval uses the bindings e=0,o=1 in the optional function arguments. The output is then taken mod 2. • This also works in python 3. By the way, how does eval need the "e=0,o=1" bindings ? Dec 3 '15 at 15:11 • @karhell It evaluates expressions like e+o, so it needs the variables to refer to numbers. – xnor Dec 4 '15 at 21:28 ## Mathematica, 91 84 bytes #//.s_:>s~StringReplace~{"+ee"|"+oo"|"*ee"|"*eo"|"*oe"->"e","+eo"|"+oe"|"*oo"->"o"}&  Looking for a way to compress this... • //. is shorter than FixedPoint. Dec 2 '15 at 11:42 ## C, 79 bytes Straightforward recursion. Relies on some (coincidental?) bitwise properties of the four allowed input characters. f(){int c=getchar();return c&4?c:c&1?f()^f()^'e':f()&f();}main(){putchar(f());}  # Shell + GNU utilities, 33 dc -eForev|tr oe OK2%p|tr 10 oe  Input is taken from STDIN. This does the same trick of reversing the input and evaluating with a stack-based calculator - in this case dc. We could replace e and o with 0 and 1, but then spaces would need to be inserted to prevent greedy parsing of the digits into the incorrect numbers. Instead e is replaced with K which is the dc command to push the current precision to the stack, which by default is 0. And o is replaced with O which is the dc command to push the current output base to the stack. This needs to be odd, so we set it to 15 with Fo before doing anything else in dc. Then it is simply a matter of taking mod 2 and printing 2%p. The only possible values are now 0 and 1, so it doesn't matter that the output base is 15. Then tr translates back to o or e. I like that if you squint your eyes, this source almost looks like dc Forever OK. ## Seriously, 24 bytes ,R'2'e(Æ'1'o(Æ£ƒ'e'o2(%I  More efficient stack manipulation could probably make this shorter, but meh, I'm happy with it. Takes input as a string, like "+*oee" Try it online (input must be manually entered) Explanation: ,R get input and reverse it '2'e(Æ replace all "e"s with "2"s '1'o(Æ replace all "o"s with "1"s £ƒ cast as function and call 'e'o2(%I push "e" if result is even, else "o"  # Ruby, 61 bytes Using recursive descent parsing and boolean algebra. def f gets(1)==?+?f^f : ~/\*/?f&f :$_==?o
end
puts f ? ?o:?e


The function reads one character from stdin at a time. If it reads a + or a *, it calls itself twice to determine odd or even. The function returns true for odd and false for even. The ^ XOR and & AND operators are used to determine "oddness" of addition and multiplication expressions respectively.

Here's an ungolfed version:

def f
x = gets(1)
case x
when '+'
f ^ f
when '*'
f & f
else
x == 'o'
end
end

puts f ? 'o' : 'e'


Thanks @Shel for pointing out a bug in the initial version.

• This doesn't work, +ee gives o. I do like the idea Dec 3 '15 at 19:39
• replace f^f with !f^f and f&f with f|f and it works. Program to run test cases: pastebin.com/ufXfd1vc Dec 3 '15 at 19:51
• Thanks, good catch! Seems I confused myself a bit there. Nice test suite too! Test-driven is the way to go, also when golfing :) Dec 3 '15 at 20:18
• @Shel Aha..! I changed back f^f and f&f and flipped $_==?e and ?e:?o instead :) Dec 3 '15 at 21:03 • Wow, learn something new every day... ruby-doc.org/core/Regexp.html#method-i-7E Dec 4 '15 at 1:34 ## Minkolang 0.14, 40 bytes I tried to do a clever eval method, but it turns out that any values added to the codebox outside of the original space will never be reached by the program counter. So I did a less clever eval method. :P $o"eo+*"r0I4-[4g1Z2*1F]l*"e"+O.
0f1f+f*f


Try it here.

$o Read in whole input as characters "eo+*" Push these characters onto the stack (in reverse order) r Reverse the stack I4- Push the length of the stack - 4 [ For loop; pop n and repeat that many times 4g Get the item at the fourth index and put it on top 1Z Pops n and pushes first index of n in stack 2* Multiply by 2 1F Gosub; goes to codebox(2n,1) to be returned to ] Close for loop l* Multiply by 10 "e"+ Add 101 ("o" is 111) O. Output as character and stop. 0f1f+f*f Does the appropriate operation then returns to F  • Woohoo! good ol' shell beats a (semi-)golfing language ;-P Dec 3 '15 at 19:50 # JavaScript, 110 106 94 bytes while(i.length>2)i=i.replace(/([+*][eo]{2})/,(o,e)=>{return"+oe+eo*oo".indexOf(o)<0?"e":"o"});  Certainly not the smallest solution, but likely the smallest solution possible in a verbose language like JavaScript! • Using non-capturing groups is good for performance but bad for code size. Better remove those ?:. Dec 3 '15 at 15:53 • agreed... and so modified. Dec 3 '15 at 16:37 • Took another look now. Your code can be reduced a bit further to while(i.length>2)i=i.replace(/[+*][eo]{2}/,function(o){return"+oe+eo*oo".indexOf(o)>=0?"o":"e"}). Or if you change to ECMAScript 6's fat arrow function, then while(i.length>2)i=i.replace(/[+*][eo]{2}/,o=>"+oe+eo*oo".indexOf(o)>=0?"o":"e"). But unfortunately the requirement says program or function, while your current code is a snippet. It should handle either input and output or argument and return value. Dec 3 '15 at 17:02 • Unfortunately to be valid on this site, we can't assume that a variable already exists. You'll have to make it a function of i as you said. Dec 4 '15 at 1:03 • @Arkain, you not need to capture a group in the regular expression as you will use the entire matched substring as one piece anyway. For the same reason there is no need to pass parameter e to the callback. Dec 4 '15 at 6:55 # O, 242019 18 bytes i2:e;1:o;~2%'o'e?  Takes input, reverses it, assigns e to 2 and o to 1 and posts it to Tumblr evaluates it as O code. Explanation: i Get input and reverse it, because O uses postfix notation 2:e; Assign e to 2 1:o; Assign o to 1 ~2% Eval and check if result is even 'o'e? Output 'e' if even, 'o' if odd  # GNU Sed, 36 : s/*oo\|+eo\|+oe/o/ t s/\W\w\w/e/ t  After posting I saw this exactly the same approach as @manatwork's Perl answer and @randomra's Retina answer. So I guess I may as well go all the way and borrow their \W\w\w as well. Thanks to @Ruud for shaving off 4 bytes. • With the parentheses gone, it now pays off to abandon extended regexp. You win 2 bytes for not escaping +, you lose 2 bytes for escaping |, but the end result is you win 1 byte for dropping option -r. Dec 5 '15 at 17:37 • @Ruud That's right. I tried it before, but didn't realise the | needs to be escaped when -r is not used. Still, 2 more bytes off the score - thanks! Dec 5 '15 at 19:19 # Haskell, 160 bytes Call f. f=until((==1).l)r r s|l s<3=s|3#s?o=r('o':3%s)|3#s?sequence["+*","oe","oe"]=r('e':3%s)|0<1=1#s++r(1%s) l=length (#)=take (%)=drop (?)=elem o=["+eo","+oe","*oo"]  ## JavaScript, 92 71 bytes f=i=>i>"0"?i:f(i.replace(/.[eo]{2}/,e=>"eo"[eval((e>"e")+"^&"[+(e<"+")]+(e>"e"))]))  It's a bit obfuscated, but I wanted to do something using eval and bitwise operators. Annotated: f = (i) => // function(i) { return i>"0" // i == "o" || i == "e" :-) - the characters * and + are both <"0" ? i // finish : f(i.replace( // recursively repeat with /.[eo]{2}/, // first occurrence of "something" followed by two values (e) => // replaced by "eo"[ // string indexing eval( (e>"e") // e == "o" ? "true" : "false" + "^&"[+(e<"+")] // e == "+" ? "^" : "&" + (e>"e") // e == "o" ? "true" : "false" ) ] // like eval(…) ? "o" : "e" ))  The repetition of (e[…]>"e") annoys me a bit, but the following is not better either (103 bytes): f=i=>i>"0"?i:f(i.replace(/e|o/g,x=>+(x>"e")).replace(/.\d\d/,e=>"eo"[eval(e+"^&"[+(e<"+")]+e)]))  So in the end, @Arkain's approach with simple substring matching is superiour. Made into a function, with some optimisations: f=i=>i>"0"?i:f(i.replace(/.[eo]{2}/,v=>"eo"[+"+oe+eo*oo".includes(v)]))  # Dart, 173 bytes f(i){var l=i.split(''),e='e',o='o';g(p){if(l[p]!=e&&l[p]!=o){var x=p+1,y=p+2;g(x);g(y);l[p]=l[p]=='+'?l[x]!=l[y]?o:e:l[x]==o?l[y]:e;l.removeRange(x,p+3);}}g(0);print(l);}  This isn't competitive, but whatever. The gist of the solution is, starting at 0, recursively replace every operator with the evaluation the pair of characters following that operator and then remove those characters from the list. # Haskell, 231 bytes Here is an approach using a serious language ;) Golfed version: p(s:_)[]=s p s(x:y)=p(r$x:s)y
r[]=[]
r('e':'e':'+':x)=r$'e':x r('e':'o':'+':x)=r$'o':x
r('o':'e':'+':x)=r$'o':x r('o':'o':'+':x)=r$'e':x
r('e':'e':'*':x)=r$'e':x r('e':'o':'*':x)=r$'e':x
r('o':'e':'*':x)=r$'e':x r('o':'o':'*':x)=r$'o':x
r x=x


Example:

*Main> p [] "+**+***+**++**+eooeoeeoeeoeooeo"
'o'


Ungolfed and pretty comprehensive version:

type Stack = String

parse :: String -> Char
parse = parse' []

parse' :: Stack -> String -> Char
parse' (s:_) []     = s
parse' s     (x:xs) = parse' (reduce $x:s) xs reduce :: Stack -> Stack reduce [] = [] reduce ('e':'e':'+':xs) = reduce$ 'e':xs
reduce ('e':'o':'+':xs) = reduce $'o':xs reduce ('o':'e':'+':xs) = reduce$ 'o':xs
reduce ('o':'o':'+':xs) = reduce $'e':xs reduce ('e':'e':'*':xs) = reduce$ 'e':xs
reduce ('e':'o':'*':xs) = reduce $'e':xs reduce ('o':'e':'*':xs) = reduce$ 'e':xs
reduce ('o':'o':'*':xs) = reduce $'o':xs reduce xs = xs  Example: *Main> parse "+**+***+**++**+eooeoeeoeeoeooeo" 'o'  Features: Pattern matching and recursion. # Jolf, 11 bytes (Noncompetitive, as the language postdates the question.) Try it here! FVyAi"oe"@\x12  (Replace \x12 with the actual character \x12. This should be done automatically in the interpreter.) Explanation: FVyAi"oe"@\x12 i input \x12 character 12 @ char code at A "oe" replace all os with 1s and all es with 2s y eval as jolf, returning the answer V return parity "even" or "odd" F get first character implicit output  # Python 3, 171145 135 bytes Not competitive, but I had fun doing it, so I just couldn't keep it to myself. Unlike the (very clever) recursive-iterator Python entry by feersum, this one reverses the input and then does a good old stack-based parsing of reverse Polish notation. def p(i): s=[] for c in i[::-1]: s+=[c>'e'if c>'a'else getattr(s.pop(),'__'+('axnodr'[c>'*'::2])+'__')(s.pop())] return'eo'[s]  • That callable() is elegant, but long. (Reversing the condition and removing not would be shorter.) Check instead if m is integer m in[0,1] would be shorter, but checking if c is value c in'eo' would be even shorter. This later being the same as c>'a' in this case. Dec 5 '15 at 12:19 • Actually there is no need for variable m and its numeric values. Put only this inside the for: s+=[c>'e'if c>'a'else{'*':o.and_,'+':o.xor}[c](s.pop(),s.pop())] Dec 5 '15 at 12:28 • @manatwork: Thanks! I didn't think I could reverse the condition, because I thought that would've meant calling s.pop() (twice) every loop. I didn't bother testing until now; but hey, the point's moot now. Dec 6 '15 at 6:56 • One question bothered me since the beginning: why using the operator  module? bool.__and__() and bool.__xor__() are handier: s+=[c>'e'if c>'a'else getattr(s.pop(),{'*':'__and__','+':'__xor__'}[c])(s.pop())]. But based on gnibbler's slicing tip, that can be changed into s+=[c>'e'if c>'a'else getattr(s.pop(),'__'+('axnodr'[c>'*'::2])+'__')(s.pop())]. Dec 6 '15 at 12:36 • @manatwork: Because I hadn't thought of that. I only considered the infix operators (^, &) and their operator counterparts, forgetting about the methods that actually implement them. Oh, and reversed() has now been dropped thanks to another of the Python golfing tips. Dec 8 '15 at 12:05 ## Haskell, 98 94 bytes Sorry to bother you with yet another Haskell attempt; just wanted to prove it is very well possible in less than 100 bytes. p(c:s)|any(<'a')s=p(c:p s) p('+':x:y:s)|x/=y='o':s p('*':'o':s)=s p(c:_:_:s)|c<'a'='e':s p s=s  Defines a function p that accepts any valid expression as parameter, and returns the result as a string of length 1. Example: *Main> p "**o++*ee*++eoe*eo+eoo" "o"  The function works by repeatedly reducing the rightmost operator in the string until no operators are left. # Add++, 46 bytes D,g,@,d"oe"$eA"e"=+o
D,f,@,bR€gbU32CjbV2%"eo":


Try it online!

The footer simply enumerates all the example inputs and their corresponding outputs.

## How it works

Like a lost of the answers here, this uses replacement and evaluation. Our main function is f, and g is a helper function. We'll use "*e*o*e*oe" (which is e) as an example.

f begins by taking the input string and reversing it, yielding "eo*e*o*e*". We then map g over each element:

g starts by duplicating the argument, to keep a copy until the final command. We then check if the argument is in the string "oe", yielding 1 for letters and 0 for * or +. We then push the argument again and check whether it is equal to "e". This result is then added to the previous check. This yields 0 for either * or +, 1 for o and 2 for e. We then take the logical OR between this value and the argument. If the value is 0, it is replaced by the argument (i.e. * or +), otherwise it is left as-is (i.e. 1 and 2).

This converts all letters in the reverse of the input into a numerical value. We then join each element by spaces, to ensure digits aren't concatenated. For our example, this yields the string "2 1 * 2 * 1 * 2 *". We can then evaluate this, using Add++'s postfix notation, yielding 8. We then take the parity of this value, yielding either 0 for even numbers and 1 for odd numbers, before indexing into the string "eo" and returning the corresponding letter.

# Python 3, 99 bytes

import re
a=b=input()
for i in a:a,b=re.subn(b and"\+(eo|oe)|\*oo"or"\W\w\w","oe"[b==0],a)
print(a)
`

Try it online!

Nice solution using regex. (python has already better solutions, go upote those)