import re


def parse_braces(sequence):
    """
    Replace all occurrences of ``x{n}`` (where x is any character) with n
    occurrences of x. Raise ValueError if the expression cannot be parsed.

    >>> parse_braces('TGA{5}CT')
    TGAAAAACT
    """
    # Simple DFA with four states, encoded in prev
    result = ''
    prev = None
    for s in re.split('(\{|\})', sequence):
        if s == '':
            continue
        if prev is None:
            if s == '{':
                raise ValueError('"{" must be used after a character')
            if s == '}':
                raise ValueError('"}" cannot be used here')
            prev = s
            result += s
        elif prev == '{':
            prev = int(s)
            if not 0 <= prev <= 10000:
                raise ValueError('Value {} invalid'.format(prev))
        elif isinstance(prev, int):
            if s != '}':
                raise ValueError('"}" expected')
            result = result[:-1] + result[-1] * prev
            prev = None
        else:
            if s != '{':
                raise ValueError('Expected "{"')
            prev = '{'
    # Check if we are in a non-terminating state
    if isinstance(prev, int) or prev == '{':
        raise ValueError("Unterminated expression")
    return result