Basic Algebraic Expansion
J - 350 char - 25 = 325 pts

Forgive me, Roger Hui, for I have sinned.

x=:0 1
f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&amp;":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@&lt;:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&amp;,e'+'@((+/@,:&amp;,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(&lt;@; ::({:u/&amp;.&gt;{.)/.~i.@#-i.@#(&gt;+&gt;:)(&lt;,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&amp;.&gt;)@([-.~;@]&lt;@(p^:(1&lt;#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&amp;;:])


The above monstrosity defines a number of variables, of which the variable f is a function satisfying the constraints in the question above. I claim the "expr^n" bonus for 25 points.

Here's the golf in action at the J REPL.

   x=:0 1
   f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&amp;":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@&lt;:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&amp;,e'+'@((+/@,:&amp;,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(&lt;@; ::({:u/&amp;.&gt;{.)/.~i.@#-i.@#(&gt;+&gt;:)(&lt;,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&amp;.&gt;)@([-.~;@]&lt;@(p^:(1&lt;#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&amp;;:])

   f '2+2'
4
   f '(5+x)+6'
x+11
   f '(x+2)^2'
x^2+4*x+4
   f '(x-5)*(3+7*x)'
7*x^2-32*x-15
   f '5*x+9*x'
14*x
   f '(2*x^2)*x^3'
2*x^5
   f '(2*x+3)^(2+3)*2^3'   NB. bonus
256*x^8+1920*x^7+5760*x^6+8640*x^5+6480*x^4+1944*x^3


Here's the gist of what's going on.


'()'...@([-.~;@]&lt;@(p^:(1&lt;#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&amp;;: - Recursively break down the expression based on its parenthesized subexpressions, and evaluate them (the ... bit, to be described below) as they are ready. ;: performs the tokenizing.
(([^:(''-:])". ::])&amp;.&gt;) - Evaluate atoms. If the atom is numeric, it is turned into a scalar number. If the atom is an operator, it is left as-is. If the atom is the variable x, it is turned into the vector 0 1. (That's why we define x=:0 1 at the start.) In general we store the polynomial a*x^n + b*x^(n-1) + ... + c*x + d as the n+1-item list d c ... b a.
e=:2 :'(&lt;@; ::({:u/&amp;.&gt;{.)/.~i.@#([-&gt;+&gt;:){.@i.&amp;(&lt;,v))^:_' - This curious conjunction takes a verb on the left and a character on the right. It finds the first instance of that character in its tokenized, paren-less input, and evaluates it with the arguments around it, and repeats until there are no more such characters to find. Thus, we iteratively simplify the expression, with order of operations controlled by order of application of e.
And then all the stuff in the front is just pretty-printing output. rplc is a standard library function for substring replacement. We can save another three chars if we're allowed to put the lowest degree terms first instead of the highest, by removing the @|..


I am honestly uncertain whether I can squeeze any more characters out of this golf. I can't think of any other approach that doesn't require a similar amount of overengineering, but that doesn't mean there isn't one. Either way, I'm pretty sure I've squeezed all the obvious characters out of this version.