平衡括号检测？

Question

所以我需要创建一个程序来确定一组括号是否平衡以及确定哪个括号是第一个 "offending parenthesis" 这意味着第一个括号不属于平衡对.

我只能想出一个程序来判断这组括号是否平衡，但想不出一个通用的检测第一个不属于一对的括号的方法。

例如：在“(())(()(”中，第五个括号是第一个有问题的括号。

我已经尝试了很多方法来找到第一个有问题的括号，但它们并不适用于每一种情况，所以如果您有更好的算法，请告诉我。我应该在考虑堆栈概念的情况下实现它。

Answer 1

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

Answer 2

按照我用来标记第一个不匹配括号的 Perl 脚本：

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

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

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

print

用法：

$ 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?

java

algorithm

stack