Balancing parenthesis detection?

Question

So I need to create a program that can determine if a set of parentheses is balanced or not as well as determine which parenthesis is the first "offending parenthesis" meaning the first parenthesis to not be part of a balanced pair.

I could only come up with a program that determined if the set of parentheses were balanced or not, but couldn't figure out a common detection method for the first parenthesis that doesn't belong to a pair.

Ex: In "(())(()(" the fifth parenthesis is the first offending parenthesis.

I've tried many ways to find the first offending parenthesis, but they didn't work for every single case, so please let me know if you have a better algorithm in mind. I'm supposed to implement this with the stack concept in mind.

I'd go left to right across the string. Adding 1 for a `'(` and subtracting 1 for a `)`. If you reach a negative value, or end with a non-zero value, then they aren't matched properly. The first case is easy, the second would require some back-tracking to find the last 0-case. — Obicere, Mar 01 '15 at 04:38
possible duplicate of [Checking string has balanced parentheses](http://stackoverflow.com/questions/1380610/checking-string-has-balanced-parentheses) — Paul Hankin, Mar 01 '15 at 05:13

A. I. Breveleri · Accepted Answer · 2021-03-02T02:25:02.163

4

1. set up a stack
2. scan the string char by char
  2.1. for each left parenthesis "("
    2.1.1. push its location onto the stack
  2.2. for each right parenthesis ")"
    2.2.1. if stack is empty then
      2.2.1.1. you have too many right parentheses
      2.2.1.2. current location is first offending location
    2.2.2. else
      2.2.2.1. pop one entry from the stack
3. after scanning the string
  3.1. if stack is empty then
    3.1.1. all parentheses balance
  3.2. else
    3.2.1. you have too many left parentheses
    3.2.2. first entry on stack indicates first offending location

edited Mar 02 '21 at 02:25

answered Mar 01 '15 at 04:12

A. I. Breveleri

747
5
6

I implemented something similar: open parenthesis is pushed to stack and closing pops it out. Another arraylist stores the indexes of the opens and removes the last one whenever there is a closing. So whichever one is remaining in that stack is returned as the offending parenthesis index. – btrballin Mar 01 '15 at 06:03
What would be the result for a example like the one presented in my answer? – JJoao Apr 13 '15 at 14:21

score 0 · Answer 2 · answered Apr 13 '15 at 14:19

Following the Perl script I use for marking the first un-matched parentheses:

#!/usr/bin/perl
use strict;
undef $/;
$_= <>;                   # slurp input
my $P = qr{[^()]*};       # $P = not parentheses

                          # repace matched parentheses by marks
while(s!       \( ($P) \)        !\cA$1\cB!gx){}
while(s!^ ($P) \( (.*) \) ($P) $ !$1\cB$2\cB$3!sgx){}

s!([()])! → $1!;          # mark the first unmatched ()
y!\cA\cB!()!;             # replace marks

print

Usage:

$ cat f
1(2(3(4(5)6)7)8(9)10(
   11(12)13)14)  (15 ( and ) 
      (16(17(18)19)
   20)21(22)23

$ parentesis f
1(2(3(4(5)6)7)8(9)10(
   11(12)13)14)   → (15 ( and ) 
      (16(17(18)19)
   20)21(22)23

Balancing parenthesis detection?

2 Answers2