Swift 6, 99 92 bytes

let f={(i:inout _)in for _ in""+i{i.replace(/\W\w\w/){"+oe+eo*oo".contains($0.0) ?"o":"e"}}}

Call it like this:

var string = "+**+***+**++**+eooeoeeoeeoeooeo"
f(&string)
print(string) // "o"

Try it on SwiftFiddle!

JavaScript (Node.js), 66 bytes

f=a=>a>f?a:f(a.replace(/(\+oe|\+eo|\*oo)|.\w\w/,(v,c)=>c?'o':'e'))

Try it online!

From Bergi & Arkain's approach

Thue, 95 bytes

*ee::=e
*eo::=e
*oe::=e
*oo::=o
+ee::=e
+eo::=o
+oe::=o
+oo::=e
>e::=~e
>o::=~o
i::=:::
::=
>i

Try it online!

MathGolf, 23 bytes

x$╟⌠%_Z)m=9*m+$y~♂*♀)+$

Input as a list of characters to save a byte.

Try it online.

Explanation:

x                 # Reverse the (implicit) input-list
 $                # Convert each character to its codepoint-integer
  ╟⌠              # Push 62 (60+2)
    %             # Modulo
     _            # Duplicate the list
      Z)          # Push 39 (38+1)
        m=        # Check for each value if it's equal to 39 (1 if 39; 0 otherwise)
          9*      # Multiply each by 9
            m+    # Add the values in the lists together
              $   # Convert it from codepoint-integers back to characters
               y  # Join it together to a string
                ~ # Evaluate and execute it as MathGolf code
♂*                # Multiply each by 10
  ♀)              # Push 101 (100+1)
    +             # Add it to the integer
     $            # Convert it as code-point integer to character ('e' or 'o')
                  # (after which the entire stack is output implicitly)

Unfortunately MathGolf lacks a replace/transliterate builtin, otherwise this could be as easy as xûoe2à<transliterate>~♂*♀)+$ (14 bytes).

05AB1E, 14 bytes

„eoDIRs„¾X‡.Vè

Try it online or verify all test cases.

Explanation:

„eo            # Push string "eo"
   D           # Duplicate it
    IR         # Push the input, and reverse it
               # (since 05AB1E evaluates in Reverse Polish Notation)
      s        # Swap so one of the "eo" is at the top
       „¾X     # Push string "¾X"
               # (`¾` is 0 by default and `X` is 1 by default. We use these instead of
               # literals, because it could otherwise push 10, 100, "001", etc. instead
               # of loose digits)
          ‡    # Transliterate "e"→"¾" and "o"→"X"
           .V  # Pop, evaluate, and execute the string as 05AB1E code
             è # Index the resulting 0/1 into the "eo" string
               # (after which the result is output implicitly)

Lexurgy, 65 bytes

a propagate:
\+ {ee,oo}=>e
\+ {eo,oe}=>o
\* {eo,ee,oe}=>e
\*oo=>o

Explanation:

a propagate:     # while last output was not the same...
\+ {ee,oo}=>e    # handle even addition
\+ {eo,oe}=>o    # handle odd addition
\* {eo,ee,oe}=>e # handle even multiplication
\*oo=>o          # handle odd multiplication

As a bonus, if you copy-paste the test cases verbatim into Lexurgy, it will not touch the expected output side of the arrow.

Vyxal, 13 bytes

‛oe₀Ŀ∑ṘṄĖ₂∆ċt

Try it Online!

    Ŀ∑        # Replace each of 
‛oe           # o and e
   ₀          # With 1 and 0
      Ṙ       # Reverse 
       Ṅ      # Join by spaces
        Ė     # Eval
         ₂    # Even? (1-n%2)
          ∆ċt # Last character of num -> cardinal (one -> e, zero -> o)

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)

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.

Shell + GNU utilities, 33

dc -eFo`rev|tr oe OK`2%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.

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.

Python 3, 171 145 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[0]]

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.

JavaScript, 92 71 bytes

f=i=>i>"0"?i:f(i.replace(/.[eo]{2}/,e=>"eo"[eval((e[1]>"e")+"^&"[+(e[0]<"+")]+(e[2]>"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[0] == "o" || i[0] == "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[1]>"e")        // e[1] == "o" ? "true" : "false"
                  + "^&"[+(e[0]<"+")] // e[0] == "+" ? "^" : "&"
                  + (e[2]>"e")        // e[2] == "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[1]+"^&"[+(e[0]<"+")]+e[2])]))

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)]))

O, 24 20 19 18 bytes

i`2: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

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

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"]

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());}

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.}

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!

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.

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"

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.

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[0]);}

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.

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.

Explanation

$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

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.

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, 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.

Mathematica, 91 84 bytes

#//.s_:>s~StringReplace~{"+ee"|"+oo"|"*ee"|"*eo"|"*oe"->"e","+eo"|"+oe"|"*oo"->"o"}&

Looking for a way to compress this...

Perl, 50 45 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

CJam, 18 17 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.