Evaluation of this expression isn't a problem :

1) Replace all of operators into one-char operators. For example, NOT into '-', TRUE into '1', etc.
It will greatly simplify coding, because of operators don't begin on char, that can be a register.

2) Recursive descent :
In function we've got bounds of the expression and we'll find result of it in this bounds.
Find the least priority operator first. This is an operator, that has least number of not closed brackets, and if we find operator with equal number of such brackets the least in priority of operators.
Then : if not found any operator, then expression has only register or constant. Calculate it.
if NOT - Result = not Evaluate(pos_of_operator, right bound),
if OR or AND - Result = Evaluate(left_bound, pos_of_operator - 1) OPERATOR Evaluate(pos_of_operator + 1, right_bound) (crazy pseudocode =) )

That's all. Of course, it's a slow method, but it's very easy - without any problems, debugging or testing i've got fast AC 0.015 sec, 300kb