You have to enclose all ANSI escape sequences in \[ .. \]
to signal to Bash that these don't take up space on the terminal.
They have to be in the format string itself, and can not be part of data expanded at prompt time (but can be in data expanded at assignment time).
For example:
export PS1="\[$BLUE_BOLD\][\A]\[$GREEN_BOLD\]\u:\[$RED_BOLD\]\w\[$YELLOW_BOLD\]\$(parse_git_branch)\[$NORMAL\] > "
To make this work for smile_or_frown, you have to refactor it into two functions, one for the color and one for the text, so that you can do "\[\$(smile_color)\]\$(smile_type)"