need help with a regex

[sde]

var str = "abc ( 123 ( 456 ) ) ( 789 )";

i need to capture the first level of open/close parens in an array. i want the output of my regext to match 2 items creating an array like this:

array[0] = "( 123 ( 456 ) )";
array[1] = "( 789 )";

[teknomage1]

I think this is best done with a stack rather than regular expressions, because regexes break down on arbitrarily nestable structures. So basically everytime you see a open paren, push onto a stack and whenever you see a close paren, pop stuff off the stack and when the stack is empty you'll have the outermost parenthetical expression.

[teknomage1]

I think this is reasonably robust. It takes a string as input and returns an array with each of the top level parenthetical expressions. It seems to handle stray parenthesis gracefully.

PHP Code:

function parenreader($input) {
    $output = array();
    $inbuffer = $input;
    $outbuffer = "";
    $stack = 0;
    while( strlen($inbuffer) > 0 ) {
        $op = strpos($inbuffer,'('); #saw an open paren
        $cp = strpos($inbuffer,')'); #saw a close paren
        #saw an open paren first
        if( $op < $cp && !empty($op)) {
            $stack++;
            $outbuffer .= ( $stack > 1 ? substr($inbuffer, 0, $op+1) : '(' );
            $inbuffer = substr($inbuffer,$op+1);
        }
        #saw a close paren first
        if( $cp < ( empty($op) ? $cp+1 : $op) ) {
            $segment = substr($inbuffer, 0, $cp+1); #save this in case we need it
            $inbuffer = substr($inbuffer,$cp+1); #move on in case it's a stray paren
            #this is part of an expression
            if( $stack > 0 ) {
                $stack--;
                $outbuffer .= $segment;
            }
        }
        #the stack is empty and we have an expression
        if ($stack == 0 && strlen($outbuffer) > 0) {
            array_push($output, $outbuffer);
            $outbuffer = "";
        }
        #No more full expressions to read
        if ( empty($cp) || empty($op) ) {
            $inbuffer = "";
        }
    }
    return $output;
} 


[sde]

i was thinking regex .. this is an interesting approach. i'll port it to javascript and give it a try tomorrow. thanks!

[teknomage1]

I'm pretty sure it's impossible to write an accurate regex for an infinitely nestable structure due to their nature. Once a regular expression is compiled it basically has no memory and all state changes are based on the character from the input stream and one character look ahead. Smart tricks like back references make them seem smarter, but they're really simplistic at their core. The device simply doesn't have enough information to balance parenthesis or html tags.