This code will correct the gross imbalance of parens without requiring to delete them all. As is, it works line by line, but would operate on a whole file if you slurped it.

#! perl -slw
use strict;

while(<DATA>) {
    my $count=0;
    chomp;
    print;
    $count += $1 eq '(' ? +1 : -1 while m[([()])]g ;
    s[(^.*?)\(]    [$1]   while $count-- > 0;
    s[(.*)\)(.*?$)][$1$2] while ++$count < 0;
    print;
}
__DATA__
test (test)
test (test
(test (test))
(test (test)
(() (()) (((()))))
( () (()) ( ( () ) ) ))
(( () (()) ( ( () ) ) )
((( test
test )))
(((test)
(test)))
[download]

All it does is count the number of opens and closes and delete enough of whichever is in excess from the beginning or end to correct any imbalance.

In most cases, that probably means that the resultant parenthesizing would not reflect the original intent, but it is difficult to see how to determine what that intent was without specific knowledge.