This always start out as fun, but rapidly descends(sic!) into a much harder, if not impossible regex problem once the full requirements become clear. If your post reflects your real requirements and they are not going to 'grow', you might be able to use something relatively simple like this?

This will handle white space delimited infix operators and (I think) unlimited nested parens. It will detect trivially unbalanced parens, but maybe not badly nested ones. Adding unary prefix operators shoudl be possible without to much effort.

#! perl -slw
use strict;

my $reTokenise = qr[\s*(\S+)(?:\s+((?i:and|or)))?];

sub parseExpr {
    my $expr = shift;
    my @tokens = $expr =~ m[$reTokenise]g;
    pop @tokens unless defined $tokens[ $#tokens ];
    return '[' . join( '.', @tokens ) . ']';
}

while( <DATA> ) {
    chomp;
    warn "Unbalanced parens '$_'" and next unless tr[(][] == tr[)][];
    s[ \( ( [^()]+ ) \) ]{ parseExpr( $1 ) }xe while m[[()]];
    $_ = parseExpr( $_ ) if m[\s];
    print;
}

__DATA__
((A or B)
(A) or B)
((A) or B)
A or B or C and D
( ( this OR that ) AND other )
( A or ( B and (C or D) ) or (E and F) )
(A or (B or C) or (D and E))
[download]

Output:

c:\test>junk5
Unbalanced parens '((A or B)' at c:\test\junk5.pl line 15, <DATA> line
+ 1.
Unbalanced parens '(A) or B)' at c:\test\junk5.pl line 15, <DATA> line
+ 2.
[[A].or.B]
[A.or.B.or.C.and.D]
[[this.OR.that].AND.other]
[A.or.[B.and.[C.or.D]].or.[E.and.F]]
[A.or.[B.or.C].or.[D.and.E]]
[download]

Although it looks like it simply replaces spaces with dots and parens with brackets, it does actually parse correctly and substitutes a composite token for expressions as it goes.

Modifying it to substitute the appropriate truth value for the expression is trivial, but since you don't indicate the nature of 'this', 'that' & 'other'--eg. numeric, T or F, true or false etc.--it wasn't possible to post that.

If you think it will be useful and want to pursue it further, I've had a hankering to see how far it could be taken before it turns into an mess.