Regular expressions: Finding "negation" of regular expression?
As another answer already states, the standard approach is: converting to a DFA, complementing, and converting back to a regular expression takes two exponential steps in the worst case (one for obtaining the equivalent DFA, and one for converting its complement to a regular expression). 

This is essentially optimal in the worst case: There are examples of regular expressions of length $n$ such that the shortest regular expression describing complement provably has length at least $2^{2^{c \cdot n}}$, where $c$ is some fixed constant; Such examples are known already for alphabets of size $2$. (Gelade &amp; Neven 2008, and Gruber &amp; Holzer 2008).  


Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008: 325-336
Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50