text:
Well that's odd... no wait, that's even!
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?

@ghosts_in_the_code No, sorry.

Is using eval OK?

@xnor Sure. Whatever works.

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.

@WGroleau oops, scratch that last comment - if we're being consistent with outputs, it's XOR and AND (even = 0, odd = 1) or XNOR and NAND (switched)

@question_asker, Correct on your second.  My bad.

Will any language don't hardcore the symbol of o be sshorter?

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.

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 accessing an element in a string is done modulo wrapping. So no need for modulo 2.

@xnor But thanks for the reverse thing. Of course this is not necessary. (I'm a litle bit tired today.)

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

How about while/../?

Doh. Me stupid. Actually used that condition while tried its sed version… Thank you, @primo.

Or even better, 1while s/\+oe.... I'm also pretty sure [+*] can be replaced with \W.

Thank you again, @primo. I think I should concentrate on a single solution once. (gema driving me mad…)

Same approach with Sed now 2 bytes shorter!

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.

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 You might as well post that as an answer. It is much different from this solution.

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 ?

@karhell It evaluates expressions like e+o, so it needs the variables to refer to numbers.

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.

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

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

replace f^f with !f^f and f&f with f|f and it works. Program to run test cases: http://pastebin.com/ufXfd1vc

Thanks, good catch! Seems I confused myself a bit there. Nice test suite too! Test-driven is the way to go, also when golfing :)

@Shel Aha..! I changed back f^f and f&f and flipped $_==?e and ?e:?o instead :)

Wow, nice golfing! What's the ~/regexp/ syntax do? I've never seen it before.

Wow, learn something new every day... http://ruby-doc.org/core/Regexp.html#method-i-7E

@Shel :) It's also frequently pointed out here that you can in fact drop the ~ and leave the regex by itself, but this prints a warning which I don't like.

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"

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)

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

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

Woohoo! good ol' shell beats a (semi-)golfing language ;-P

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 ?:.

agreed... and so modified.

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.

I thought there might be a way to use indexOf to reduce the operation check length, but I got distracted by work.  ;) As for the use of the arrow operator from ES6, I'm still leary about that since overall ES6 support isn't stable across the board.... but it works!

Just one other thing. As it works out, a snippet of running JS code IS a JS program! Supplying the input is as simple as adding a
var i="*+eeo";
or providing some other means of setting i. The output is the value of i.
We could always spend a few more characters and prefix this with
i=>...

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.

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

Have a look at my answer for a polished-up version :-)

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.

@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!

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

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

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.

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

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

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

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

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.

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.

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.

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.

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)

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!

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

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)

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

Swift 5.9, 99 bytes
let f={(i:inout _)in
for _ in""+i{i.replace(#/\W\w\w/#){"+oe+eo*oo".contains($0.output) ?"o":"e"}}}

Call it like this:
var string = "+**+***+**++**+eooeoeeoeeoeooeo"
f(&string)
print(string) // "o"

Here's a JDoodle link, with test cases. (Note that the tests will be output in a random order, since Swift dictionaries are unordered.)


text:
Bracket balancing
You will be given a (possibly empty) string containing brackets ([{()}]) and any other characters (A-Z, a-z, 0-9, punctuation). You need to check if it adheres to the following rules:

Non-bracket characters are ignored.
Every open bracket [{( has a closing bracket )}]. So []( is not allowed.
Brackets are nested properly. [(]) is not allowed.
Curly brackets cannot contain square brackets within them. Simple brackets cannot contain either curly or square brackets within them. So [({})], [{[]}] and ({}) are not allowed. Brackets can be nested with similar brackets, so [[{((()))}{{(())}}]()]{()} is allowed.

Output is a single truthy/falsey value as per your choice.
Shortest code wins.

Test cases
b[[a{(/)}(())+={{}-}],] -> Valid
([h][e][l][l][o]) -> Invalid
[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Valid
hi -> Valid

Possible duplicate of Fix unbalanced brackets

@FUZxxl That looks like a much harder challenge. I feel like there is another dupe somewhere though.

@MartinBüttner Yes, it can. I've added some testcases. And did you find the duplicate you were looking for?

@ghosts_in_the_code No, but I haven't kept searching. Although I think if there is one that checks multiple bracket types it doesn't give them different priorities, so I think this should be fine.

@MartinBüttner: This challenge might be what you were thinking of.

@IlmariKaronen Thanks, but I don't think I've ever seen that one.

I think we should close the other question as a duplicate of this; this is better because it has fewer bonuses.

@ThomasKwa Please see this link. http://meta.codegolf.stackexchange.com/questions/7653/duplicates-of-each-other-wrt-bracket-balancing

Retina, 84 bytes
^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

Try it online.
This is a fairly straight-forward (but golfed) extension of the basic parentheses-checking .NET regex.
While this is quite possible with balancing groups, Perl's recursion definitely has the edge here. However, either approach is beaten by ditching the elegance of a single regex match in favour of reducing the input gradually via repeated substitutions, as Digital Trauma's sed answer does. This can be implemented in 34 bytes in Retina, but I'm hesitant to post the code myself, as I didn't come up with the idea.

Retina, 34
Firstly, credit where credit is due:

@ןnɟuɐɯɹɐןoɯ who first posted this approach.
@MartinBüttner who suggested this exact answer but was too good of a sportsman not to post it himself.

I independently (later) came up with the same approach in sed, so I hope I'm not treading on any toes (big or otherwise) by posting this:
[^][(){}]

+`\(\)

+`{}

+`\[]

^$

So now with a sudo apt-get install mono-complete and git clone https://github.com/mbuettner/retina.git I have a working retina on my Ubuntu VM.  Here's the test output:
$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$

@ThomasKwa See the test output.  I believe the code is correct and all testcases are passing.  Was there a particular problem you see in the code, or particular testcase you think will fail?

@ThomasKwa I didn't port their code, because I have no clue what any piece of ESMIN does. I just wrote this code based on what it looked like it would do, so I don't think there's any reason this should have the same bug.

Wow, @MartinBüttner, you got it right! Yeah, I thought that recursively replacing matching brackets inside-out was most logical. A quick tweak to fit the code specs made it work.

, 43 chars / 62 bytes
!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

Try it here (Firefox only).
Nope.

However, if I use newly implemented features, I can get down to 28 chars / 47 bytes:
!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”

Ohhh, are you removing the matching parentheses from inside out? That would be a mere 34 bytes in Retina: http://pastebin.com/bU77LzbR

Sed, 53
s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

Here I am claiming that since sed does not really have a concept of truthy/falsey, then I am defining the empty string to mean truthy and all other strings to mean falsey.
If that is not acceptable, then we can add a couple of lines, thus:
Sed, 66
s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

This outputs 0 for false and 1 for true.

See my comment on molarmanful's answer for the Retina version of the exact same solution (at 34 bytes; printing 0 or 1). I can't say who should post it, but it should probably be one of the two of you.

CJam, 27 26 bytes
"(){}[]"q1$f&_,@2/e*{/s}/!

This prints 1 (truthy) or 0 (falsy). Try it online! or verify all test cases.
How it works
"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.

Japt, 42 37 bytes
Saved 5 bytes with a feature I didn't realize my own language had... Thanks for adding it, @Downgoat!
Japt really needs better RegExp support...
!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

Try it online!
How it works
               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression

C99, 226 208 207 Bytes
This is my first time ever trying to golf something
#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

Readable:
int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

There is a buffer overflow but it doesnt seem to affect anything - I believe this is due to alignment.

You can omit the space in char* s

Didn't know that - thanks

Python 3, 196 170 160 154 bytes
Awkwardly long, thanks to Mego for saving 6 bytes:
d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)

Perl, 50 + 1 = 51 bytes
$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

Requires the -p flag and prints 1 for truthy and nothing for falsy results. I'm counting -p as one, because it can be combined with -e:
> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

The code is basically just a plain regex match against the input, using Perl's nifty recursive regex feature.
Thanks to Dennis for helping me test this and golf the Perl boilerplate.

Python 3 : 120 bytes
Building on @Adnan's answer, re proved shorter to use:
import re
x=re.sub('[^[\](){}]','',input())
for i in('()','{}','[]'):
 while x.find(i)>=0:x=x.replace(i,'')
print(x=='')

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Does the fishy road have an end?
I love ><>, ><> is life! 2D langages are amazing!
In this challenge, you will have to say if a "fishy" road has an end,
while code-golfing.
Definition
A fishy road is constructed with tiles, including the following ones:
v (go down)
> (go right)
^ (go up)
< (go left)
/ (mirror)
\ (mirror)

Any other character (except -|+) may be considered as a distraction, like some flowers (or fish heads) on the border of the road.
A road always start on the upper-left corner of a rectangular grid, delimited by -|+symbols. The road has an end if, by following it, you end up on a border, else, you'll be trapped in an infinite path.
Finding your way on the road is accomplished by following directions given by v>^<and mirrors. A mirror will reflect by 90° depending on where you came from. Here's how it works (using v>^<to show directions):
 ^    ^
>/<  >\<
 v    v
</>  <\>
 ^    ^

A road might be looking like this if it ends:
+--------------------+
|>\/  this way >\/>  | this one ends here
| v^            \/   |
| v^   ^.^           |
| \/\         >v     |
| /\/         ^<     |
+--------------------+

An infinite loop :
+--------+
|>>\ This|
|\\   is |
|  \\ a  |
| \ /trap|
+--------+

Specifics
A road doesn't necessarily consist only of instructions. Spaces or letters can be used to complete it. This means you have to continue moving in the same direction except if you cross a character in <v^>-|.
There will always be one of v>^< in the upper-left corner, < or ^ implies this road ends.
You may submit a function taking a string as parameter, or a standalone program using STDIN/whatever is the closest alternative in your language.
Your submission must return or print on STDOUT truthy/falsy values when it's done. Truthy values meaning the road has an end, while falsy means it is an infinite loop.
Test cases
+--------------------+
|>\/  this way >\/>  | this one ends here
| v^            \/   |
| v^   ^.^           |
| \/\         >v     |
| /\/ ><>     ^<     |
+--------------------+
    True

+--------+
|>>\ This|
|\\   is |
|  \\ a  |
| \ /trap|
+--------+
    False

+--+
|<v|
|^<|
+--+
    True

+--+
|>v|
|^<|
+--+
    False

+----------+
|v Hello \ |
|\\/\/   / |
| \/\\   \ |
|/  // >\  |
|  ^/\>\\/ |
|\  /\/\/  |
+----------+
    False

+-----+
|>\/\\|
|//\\/|
|\/\\\|
|//\//|
|\/\/ |
+-----+
    True

2 test cases added as suggested by @MartinBüttner
+----+
|v   |
|\\  |
|//\ |
|\\v |
| \/ |
+----+
    False

+----+
|v   |
|\\  |
|//\ |
|\\^ |
| \/ |
+----+
    False

Test case inspired by @ETHproductions
+-------------------------+
|><>                      |
|something smells fishy...|
+-------------------------+
    False

Standard loopholes are forbidden (as always).
The winner will be the one with the shortest code in bytes.
(it would be amazing to see a ><> answer :))

Related -- http://codegolf.stackexchange.com/q/62386/42963 and http://codegolf.stackexchange.com/q/57952/42963

This better get a ><> answer...

@ConfusedMr_C Would put on myself if I knew this langage :/. Maybe if I find time ^^'

I guess transforming the input into ><> and then calling the ><> interpreter (without including the code of that in the count) would be a loophole?

@PaŭloEbermann For it to not be a loophole, you would need to count the character in the interpreter, or using a langage with a built-in ><> interpreter, and I don't think it exists ^^.

JavaScript, ES6, 177 161 145 bytes
f=(s,i=1,M=[],D)=>D==5||!~M[O="indexOf"](D+i)&&f(s,i-[M.push(D+i),L=s[O]('|'),-L,1,-1][D=`431255${5-D+'X3412'[D]}`['><^v-|/\\'[O](s[i+L])]||D],M,D)

We can detect a cycle by traversing the path and detecting a repeat of the tuple

location
coming-from direction

That is, if we are entering some position (x,y) coming from some direction D for the second time, we know that this cycle will repeat forever. Therefore, the code keeps track of all locations that were visited, and from what direction, and checks against that record each time a new space is visited.
The directions up, down, left, and right are assigned the numbers 1, 2, 3, and 4. The code considers the current symbol being visited (s[i+L]) and changes the current direction (D), then the new direction is used to recursively call the function and evaluate the next space. 5 as a direction indicates a wall, and a true termination of the program.
Here is an explanation of less-golfed code:
f=
(s,     // input string
 i=1,   // current location as offset string index
 M=[],  // record of previously visited spaces
 D      // current direction
  )=>(
    L=s[O="indexOf"]('|'), // find arena width `L` by index of first `|`

    // if D is 5, return true, or...
    D==5 ||

    // if direction + position is not new, return false
    !~M[O](D+i) &&

    // otherwise, save this direction + position
    M.push(D+i) &&

    // recursively call `f` with new direction and position
    f(s,
      i-[,L,-L,1,-1][D=            // modify position based on active direction
        `431255${5-D+'X3412'[D]}`  // from these possible directions...
          [                        // chose the one at the index...
            '><^v-|/\\'[O](        // based on the index of the symbol
                           s[i+L]  // of the current character
                                 )
          ]
        ||D     // or preserve old D if symbol is not directional
      ],
      M,D)

The template string `431255${5-D+'X3412'[D]}` has a nested expression that handles the mirrors: because the directions are numbers, they can also be used as indexes. The expression 'X3412'[D], evaluates to the 8th character in the possible-direction string, and so corresponds to \, the 8th character in the symbol string '><^v-|/\\'). The expression says,

If current direction D is 1 (up), then the new direction on hitting a \ mirror will be 3 (left)
If current direction D is 2 (down), then the new direction on hitting a \ mirror will be 4 (right)
etc.

The other mirror / would use the expression 'X4321'[D], but since that's simply an ordered count-down from 4, we can express it more simply as 5-D.

Non-compliant ><> answer
You wanted ><>, I give you ><> !
I believe the only sane way to do this in ><> is by copying the input in the codespace and letting the interpreter decide by itself if the input leads somewhere. Since ><> doesn't implement threading anymore, that leaves us with a big problem : if the input has a loop, we'll get stuck into it.
These considerations taken into account, I decided to make a solution compatible with ><> online interpreter so that it would be possible to assert if the interpreter is stuck in the input or just taking ages to do everything. I also had to add trailing lines to the code so the online interpreter shows the added code and doesn't crash when trying to write to it.
Oh and since I'm clearly disqualified by now, I didn't bother with golfing the code.
Without further ado, the code in all its glory :
50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
              ^

To use it, copy it in the online interpreter, add enough trailing lines to handle your input, submit the code, give it the input as ;-separated lines and enjoy the ride.
A few tests :

With
+--------------------+
|>\/  this way >\/>  | this one ends here
| v^            \/   |
| v^   ^.^           |
| \/\         >v     |
| /\/         ^<     |
+--------------------+`

Final codespace :
50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
            ^
 ....................
.>\/           >\/>  .
. v^            \/   .
. v^   ^ ^           .
. \/\         >v     .
. /\/         ^<     .
 ....................

Outputs "true" and stops.

With
+--------+
|>>\ This|
|\\   is |
|  \\ a  |
| \ /trap|
+--------+

Final codespace :
50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
            ^
 ........
.>>\     .
.\\      .
.  \\    .
. \ /    .
 ........

Loops forever.

Even if it isn't compliant, I love your source ! Thanks for this entry ! It is sad that it loops forever when the it should be falthy, but good job anyway ^^.

I updated the online fish interpreter. It now supports multiline input

@Suppen Hey, nice ! Thanks for the increased max speed too !

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Write out the Thue-Morse sequence
There's quite a few challenges on this site that ask you to print out a sequence, and this is no exception.
(The following explanation of the sequence for this challenge assumes the symbols in the sequence are 0 and 1.)
The recursive definition of the Thue-Morse sequence is that
T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

A more direct definition is that the sequence from 0 to 2**m-1 and 2**m to 2**(m+1)-1 are binary complements. So 0 is followed by 1, 01 is followed by 10, 0110 is followed by 1001, and, skipping ahead a bit, 0110100110010110 is followed by 1001011001101001.
The challenge is to write a program or a function that prints out the Thue-Morse sequence for the first n elements, where n is any non-negative integer. The output can use any two symbols, as shown in the examples below.
Examples
>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

Rules

The input will be any non-negative integer. You can assume all inputs are valid.
The output must be the first n elements of the Thue-Morse sequence, using any symbols that are convenient. If you like, you can also add a separator. In my examples, I have not.
Note: This rule allows lists (like those of Python), as , is a valid separator and I don't mind leading or trailing characters, such as [ and ] in the output.
This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!
Catalogue

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='
'+c.body.replace(OVERRIDE_REG,'')+'
'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery(''+lang+'').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Related.

in simpler words you could say: the function is recursive, negate the input and append it.

@Eumel yeah, but that might give people too big a hint. I do want to see some variety in the solutions.

Borderline dupe

@PeterTaylor In what way? One possible answer to the linked question is the Thue-Morse sequence, but this question is to generate the Thue-Morse and nothing else.

Well, I did say you could put separators in the sequence and the ,  between list items is a separator. I'll allow it. Let me edit the question to indicate this. @ThomasKwa

Because some of the answers to the previous question can be used to answer this question with trivial changes, and all answers to this question can be used to answer the previous question with trivial changes.

Do they have to be single symbols, or will any two easily distinguishable non-empty strings work?

@SuperJedi224 That's a good point. Any two distinguishable non-emergency strings are alright

Does it have to be 1 and 0, or can a and b work?

@EasterlyIrk You are allowed to used any two distinguishable non-empty strings, including a and b.

@Sherlock9 okay, thanks.

Pyth, 6 bytes
xMjR2Q

Try it online: Demonstration
Based on the solution from @ThomasKwa and a variation of @FryAmTheEggman.
It uses the following formular: the i-th digit in the Thue-Morse sequence is: xor(digits of i in base 2).
Explanation:
xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

CJam, 17 9 bytes
ri{2b:^}/

or
ri,2fb::^

Test it here.
Explanation
This uses the alternative definition given on Wikipedia, based on the parity of the number of 1s in the binary representation of the n.
ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

The alternative solution uses , to turn n explicitly into a range [0 ... n-1] before using infix operators to compute the binary representations and the XOR without needing a block.
Bonus Solutions
Here are some solutions based on other definitions. If there are two solutions, the shorter one will blow up memory very quickly (because the precomputation generates 2^n bits before truncating to n).
As an L-system with 0 --> 01 and 1 --> 10:
ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

By negating and appending the previous part:
ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

Using the recurrence relation given in the challenge, using divmod and XOR to distinguish between the two recursive definitions:
ri{Ta{2md\j^}j}/

(Although, of course, this recurrence relation is just a different way to express the Thue-Morse sequence as the parity of the 1-bits in the binary representation of n.)

The memory-wasteful solution was my first thought as well, but I figured using over half a terabyte of memory to compute the output for 42 (assuming a bitset) would be pretty unreasonable.

@JohnE Problem solved. ;)

:^ makes me happy. On another note, holy crap, that's a cool algorithm.

@QPaysTaxes not :^}?

@TheLethalCoder That makes me happy too

LabVIEW, 15 LabVIEW Primitives
now as super fancy gif with a probe

Could you explain how this would be tested?

option 1: get labview test version and rebuild it, Option: suggest a way how i can send this to you as .exe or .vi (for the latter you have to get labview as well)

Really I would just like to see how this behaves when it runs. Would recording a GIF be illustrative?

that a great idea i just did that and will up it in a sec

Dyalog APL, 8 7 bytes
≠⌿⍴∘2⊤⍳

This is a monadic train that expects an index origin of 0 (⎕IO←0). The equivalent non-train function is {≠⌿(⍵⍴2)⊤⍳⍵}.
Explanation:
      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

Output is a space-separated list of 0 and 1. Try it here.

Mathematica, 35 21 bytes
Mathematica has a built-in for the Thue-Morse sequence!
Array[ThueMorse,#,0]&

Original answer:
#&@@@DigitCount[Range@#-1,2]~Mod~2&

J, 12 11 bytes
@MartinBüttner saved a byte.
~:/@#:"0@i.

This is a monadic (meaning unary) function, used as follows:
   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

Explanation
I'm using the alternative definition that Tn is the parity of the number of 1-bits in the binary representation of n.
~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

{.(,-)^:] works for 9 bytes with some rule stretching (which has been allowed). E.g. for 5 it outputs 5 _5 _5 5 _5. (Added only as a comment because of the rule stretching.)

Japt, 29 11 bytes
Uo ®¤¬r@X^Y

Try it online!
Outputs directly as an array, which saves about 4 bytes.
Ungolfed and explanation
Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`.
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

Edit: You can now use the following 8-byte code (not valid; feature published after this challenge):
Uo ®¤¬r^

you might want to update your explanation

@Eumel I already did...?

the code you explain and the code above look different

@Eumel There, is that better?

thats perfect :)

Pyth, 11 10 bytes
m%ssM.Bd2Q

Outputs as a Python-style list.

I tried using XOR over the binary string, but I don't know nearly enough about Pyth to do that. This is much shorter anyway. +1

@FryAmTheEggman Ah, I didn't know about F because I searched for 'reduce'. You could post as CW...

Haskell, 39 36 35 bytes
take<*>(iterate([id,(1-)]<*>)[0]!!)

Try it online!
How it works: start with [0] and apply the x ++ invert x-function n times. Take the first n elements from the resulting list. Thanks to Haskell's laziness only the first n elements are actually calculated.
Note: the first <*> is in function context, the second in list context.
With GHC v8.4 (which wasn't available at the the time of the challenge) there's a 34 byte solution:
take<*>(iterate(id<>map(1-))[0]!!)

Edit: -3 resp. -4 bytes thanks to @Laikoni. -1 byte thanks to  @Ørjan Johansen.

(\x->x++map(1-)x) can be shortened to ([id,(1-)]<*>) or (id<>map(1-)) with GHC 8.4.

take<*>(iterate([id,(1-)]<*>)[0]!!)

Pari/GP, 33 bytes
n->[sumdigits(x,2)%2|x<-[0..n-1]]

Try it online!

K5, 27 13 bytes
{x#((log x)%log 2){x,~x}/0}

Calculating the sequence is pretty easy, the problem is avoiding computing too much. We can recognize that the easy expansion of the sequence gives us a sequence of strings which are successive powers of two in length. Taking the log base 2 of the input and rounding up will give us enough to work with and then we can cut it down to the appropriate size:
  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

Edit:
A parity-based solution:
~=/'(64#2)\'!

In action:
  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Note that since K5 doesn't have an arbitrary convert-to-binary primitive I have to specify, for example, a 64-bit decoding. K5 doesn't use arbitrary precision math, so there will be a limit to the size of inputs we can deal with in any case.

Octave, 33 31 bytes
Saved 2 bytes thanks to Thomas Kwa.
@(n)mod(sum(dec2bin(0:n-1)'),2)

Haskell, 54 bytes
Less compact than nimi's solution, but I did not want to deny you this piece of functional code obfuscation. Works for any pair of objects; e.g. you can replace (f 0.f 1) by (f 'A'.f 'B').
Based on the definition that the first 2n digits are followed by the same sequence of digits inverted.
What we do is build up two lists side-by-side; one for the sequence, one for the inverse. Continuously we append increasingly long parts of one list to the other.
The implementation consists of three definitions:
t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

Function t accepts any number and returns the Thue-Morse sequence of that length. The other two functions are helpers.

Function f represents either list; f 0 is for the sequence, f 1 for the inverse.
Function g takes care of appending increasingly long repetitions of one list to the other.

Fiddle: http://goo.gl/wjk9S0

MATL, 9 bytes
This language was designed after the challenge.
Approach 1: 13 bytes
This builds the sequence by concatenating negated copies of increasing-size blocks.
itBFw"t~h]w:)

Example
>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explanation
i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

Approach 2: 9 bytes
This uses the same approach as Alephalpha's answer.
i:1-B!s2\

Example
>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explanation
i           % input "N"
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

Ruby, 33
->n{n.times{|i|p ("%b"%i).sum%2}}

Call like this:
f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

Uses the fact that the parity of binary numbers forms the thue-morse sequence.
Separator character is newline. Converts number i to a binary string, then calculates the sum of all ASCII codes, modulo 2.
If newline is not an acceptable separator, the following has no separator for an additional 2 bytes:
->n{n.times{|i|$><<("%b"%i).sum%2}}

Burlesque, 21 bytes
{0}{J)n!_+}400E!jri.+

Examples:
blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

Explanation:
{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

Without the jri.+ part you will run out of memory (because it will compute the morse sequence of length incredibly huge number). But since Burlesque is lazy just asking for the first n-element will work anyway.

Nice. Similar to my Haskell solution. However, I repeat only 99 times to save one byte.

, 11 chars / 23 bytes (non-competitive)
Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).
The circles are strong with this one.

Perl 5, 62 49 bytes
Yeah, not the best language for this one, but I still like the way it came out. Requires 5.14+ for /r and say.
sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

Using the parity definition, requires 5.12+ for say:
sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

C, 88 83 bytes
Calculates the parity for each individual position.
i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

Fiddle: http://goo.gl/znxmOk

Retina, 70 69 bytes
Using the definition as an L-system with initial word 0 and productions 0 --> 01 and 1 --> 10.
^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

Input is taken in unary.
You can run the code from a single file with the -s flag. Or just try it online.
Explanation
^
0;

Prepends 0; to the input, where 0 is the initial word and ; is just a separator.
(T`d`ab`^(.)+;(?!(?<-1>.)+$)

The ( indicates that this is the beginning of a loop (which repeats until the loop stops changing the string). This stage itself turns 0 and 1 into a and b respectively (because d expands to 0-9). It does this as long as current word (whose length is measured with (.)+ is shorter than the input (i.e. as long as we can't read the end of the string by matching as many 1s as we have in the word).
a
01

Replace a (stand-in for 0) with 01.
)`b
10

Replace b (stand-in for 1) with 10. This is also the end of the loop. The loop terminates once the condition in the transliteration stage fails, because then all 0s and 1s will remain unchanged and the other two stages won't find anything to match.
!`^(?=.*;(.)+)(?<-1>.)+

The last step is to truncate the word to the length of the input. This time we measure the length of the input with (.)+ in a lookahead. Then we match that many characters from the beginning of the string.

Prolog (SWI), 115 bytes
Code:
N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

Explained:
N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

Example:
p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

Try it online here

Jelly, 4 bytes
ḶB§Ḃ

Note that this challenge is older than Jelly.
Try it online!
How it works
ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

Common Lisp, 50 bytes
(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

Try it online!

V (vim), 35 29 bytes
C0<esc>qqy$V!tr 01 10
P|q@-@q@-lD

Try it online!
-6 bytes from Leo.
Prints the first \$n\$ elements.
The sequence is basically a string replacement and append, so it does that \$n\$ times using tr and then truncates the sequence to \$n\$ digits.

Nice one, here's how to get it shorter :) Try it online!
Main trick is the use of @- (from this tip), then C is equivalent to Di, the : in V:! is superfluous, and I've played around with the copy-paste-move to avoid the need for gJ

@Leo nice golfs.

Par, 8 bytes
✶u[Σ_✶¨^

Explanation:
✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

Outputs something like:
(0 1 1 0 1 0 0 1)

Math++, 86 bytes
Uses 0.0\n for 0 and 1.0\n for 1
?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

Matlab, 42
I am using the fact that it is the same as beginning with 0 and then repeating the step of appending the complement of the current series, n times.
t=0;for k=1:input('');t=[t;~t];end;disp(t)

You can replace the disp(t) by t I think...

Arcyóu, 50 55 bytes
I had to add 5 bytes to get it to work correctly :(
(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

Explanation (with Pythonesque pseudocode along the side:
(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence

Bash, 71 66 bytes
Based on the definition that the first 2n digits are followed by the same sequence of digits inverted.
x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

$1 as a parameter is the desired number of digits.
Fiddle: http://goo.gl/RkDZIC

Batch, 115 + 2 = 117 bytes
Based on the Bash answer.
@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

Needs an extra /V in the invocation to allow the use of !s.

ES6, 53 bytes
f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

Recursion seemed simpler than a loop.

Husk, 6 bytes
moF≠ḋŀ

Try it online!
Using infinite list:
↑¹!¡S+m¬;0

Try it online!

Python 3, 84 80 60 bytes
Since nobody else was using characters other than 0 and 1, I decided to write my own answer. Here, I use the characters o and t, but I was quite tempted to use b and o, or p and o :P
This is a parity checker in 60 bytes.
lambda n:''.join("ot"[bin(i).count("1")%2]for i in range(n))

This is a string rewriting algorithm in 109 bytes.
def t(n):
 r="o";s=""
 for i in range(len(bin(n))):
  for c in r:s+="otto"[c>"o"::2]
  r=s;s=""
 return r[:n]

K (ngn/k), 16 bytes
{2!+/'(x#2)\'!x}

Try it online!

I think {2!+/(x#2)\!x} works for the non-zero inputs, potentially saving two bytes.

Stax, 5 bytes
╩0ΔΔ(

Run and debug it at staxlang.xyz!
Unpacked (6 bytes) and explanation:
mv:11I
mv        Map block over range [0,n):
  :1        Popcount
    1I      Is odd?
            Implicit print with newline

1I is bitwise and with 1. 2% would work just as well, also packing to 5 bytes.

Python, 43 bytes
def f(n):n>0==f(n-1);print(n.bit_count()%2)
Attempt This Online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
How varied is my obstacle course?
Background
I have constructed a simple obstacle course by placing boxes in a rectangular room.
Now I want to count the number of essentially different ways in which it can be solved.
I need you to write me a program for that.
Input
Your input is a non-empty rectangular array of the characters .#.
The dots . are empty space, and the # are obstacles.
A path through the obstacle course begins at the top left corner and ends at the bottom right corner, and goes only right or down.
Also, a valid path cannot go through an obstacle.
Here are some examples drawn with +-characters:
Valid path  Invalid path  Invalid path  Invalid path
++........   ++........    +++++.....    ..+.......
.++++++#..   .+.....#..    ....+++#++    ..++...#..
......+#..   .+.++++#..    .......#.+    ...+++.#..
....#.++++   .+++#.++++    ....#....+    ....#+....

Two paths are essentially similar1 if one can be transformed into the other by moving one + at a time.
The intermediate paths must also be valid, so you can't bend a path over an obstacle.
For example, the first two paths here are essentially similar, but the third is essentially different from them, since it can't be wiggled over the two obstacles:
++........   +.........   +++++++++.
.+++++.#..   ++.....#..   .......#+.
.....+.#..   .++++++#..   .......#++
....#+++++   ....#.++++   ....#....+

Output
Your output is the number of essentially different paths through the obstacle course.
In other words, if all the valid paths are divided into classes of essentially similar paths, the output is the number of classes.
Note that this number may be 0, if there are no valid paths.
Rules and scoring
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
There are no time bounds, except that you should evaluate your program on every test case before submitting it.
Test cases
....
....
.... => 1

...#
....
...# => 0

#..#
..#.
.... => 0

......
......
..##..
......
...... => 2

......
...#..
......
..#...
#..... => 3

......
..#...
......
....#.
#..... => 4

.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0

......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7

.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17

..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10

.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16

1 The correct technical term is "homotopic".

What do you mean by "moving one + at a time"? Does this imply that essentially similar paths must be the same length?

@PeterTaylor All paths have the same length, since they can only go down and to the right. By "moving one +" I essentially mean that one corner of the path is inverted into a corner of the opposite direction.

@Peter: Since you can only go right or down, all paths are the same length.

Snails, 53 49 bytes
A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

For once, I did not have to use t, the dreaded teleport instruction. As a result, the test cases finish instantly instead of taking aeons.
Ungolfed:
A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

The options A^ mean to start at the upper-left corner and count all matching paths. The main idea is to check a canonicity condition for the paths. I honestly did not expect it to work, but it nailed the test cases, so.... What it tries to check for is that, within the current path, the greediest route has been selected, i.e. going right as many times as possible, down as many times as possible, etc. without crossing over any obstacles. This is done by checking, after moving right 1 or more times and then down 1 or more times, that the next square (which must be to the right) could not have been reached by going right one more time in the previous rightward segment. The analogous condition is also checked after moving right and then down.

talk about the right language for the job!

Python 2, 170 131 112 bytes
def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

A function, f, taking the obstacle course as a list of rows, and returning the number of essentially different paths.
Explanation
The basic concept is this:
We choose a certain obstacle, o, such that there are no other obstacles in the box bounding o and the top-left corner.
+--+....
|..|....
+--#<==== o
.....#..
.#......
........

We then consider the two sub-courses to the east and to the south of o.
We only consider either of these sub-courses if o can actually be crossed from a direction that leads to them, that is, crossed from the north to get to the east, and crossed from the west to get to the south.
We solve the problem for each of the selected sub-courses, and return the sum of the results.
These numbers correspond to the number of essentially different paths when crossing o from the left and from the right, respectively,
therefore the two resulting sets of paths are essentially different.
Since there are no obstacles between the starting point and o, there is a path between the starting point and any entry point into each of these regions, and all such paths that lead to the same point are essentially similar, hence the above sum is the complete number of essentially different paths in the entire course.
                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/
////////

Things are slightly complicated by the fact that the obstacle course alone doesn't convey all the information needed.
For example, consider course B in the diagram above.
Taken by itself, we can't determine whether each of the obstacles can be crossed from the north.
If B were the input course, then, since all paths start at the top-left corner, neither obstacle could have been crossed from the north, but, since we can reach B from either side of the left obstacle when crossing o from the east, we should treat this obstacle as though it can be crossed from the north when solving the course; the same doesn't hold for the right obstacle, however, which can't be crossed from this direction.
We convery this extra information by specifying, along with the obstacle course, the number of characters along the first row, starting from the left, that the path can start at.
In the diagram above, this is depcited as the solid line next to each course.
While, technically, we also need to specify the corresponding number of characters along the first column that the path can start at, as in the case of sub-course A, in practice we always selected the highest obstacle, so this information is not required.
The actual selection of o is as follows:
We pretend that each row, other than the last, is followed by an obstacle (i.e., has a # appended to it), and select the first obstacle in the resulting course, in reading order.
For rows (other than the last) that had no obstacle originally, this effectively mean that we skip them (while noting that the path below may start at any character along the top row).
Eventually, we end up with a course that has a single row with no obstacles, for which there is only one possible path.

this is pretty much the solution i was considering. I knew someone would post it before I got a chance to.

CJam, 85 84 82 81 80 79 bytes
qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Try it online. Or run the entire test suite.
The efficiency of this solution is probably quite horrible but it solves each test case within a few seconds.
Explanation
I'll have to add a full breakdown of the code later, but the algorithmic idea is this:

Let the width and height of the grid be W and H, respectively.
We generate all possible paths as the distinct permutations of W-1 copies of 0 and H-1 copies of W-1 (where 0 represents a horizontal step and W-1 a vertical step). We walk all of those paths by repeatedly taking the first element of the grid and then skipping step cells in reading order (where step is 0 or W-1). We discard all paths which contain a #.
Then we repeatedly remove one group of similar paths (which will be all paths similar to the first of the remaining paths). Checking for similar paths gets a bit easier by relaxing the condition for them slightly: instead of checking whether one x has moved, we check whether the paths differ in exactly two places. If that is the case, those two places will have a vertical and horizontal move swapped. This causes the entire segment between those moves to be shifted diagonally by one cell. But if both of those paths are valid, shifting any part of the path by one cell diagonally cannot cross an obstacle, so they are similar. We still need to find the transitive closure, so we keep doing that until we find no more similar paths before moving on to the next group.
Finally, we count the groups we've found, which we left at the bottom of the stack.