Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!bionet!ames!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.perl
Subject: Re: Matching parentheses
Message-ID: <12435:Nov3011:26:5990@kramden.acf.nyu.edu>
Date: 30 Nov 90 11:26:59 GMT
References: <1990Nov28.150131.28981@ugle.unit.no> <16600@csli.Stanford.EDU> <5209:Nov2909:58:4190@kramden.acf.nyu.edu>
Organization: IR
Lines: 11

It occurs to me that the solutions posted so far will take forever on
long strings. Here's a linear-time solution:

#!/bin/sh
( echo '0'; fold -1 | sed 's,[^()],,
s,(,1+p,
s,),1-p,' ) | dc | ( grep -s -e - && echo 'unbalanced' || echo 'balanced' )

(Whaddya mean, this isn't comp.unix.shell? :-) )

---Dan