用PERL如何实现括号的正确匹配，相当于数学中的小括号，请多发表意见！！！

minirain

如式子：
表达式1、{{名称为括号A ...}}......字符串{{......}}；
             A                      A                 B      B
表达式2、{{...... .......{{...........}}...........}}
              A               B             B           A
其中A、B为正确匹配的括号名称，......为字符串，一段文字有很多表达示1和表达式2组成，用Perl 正则表达式如何实现括号（{{）与回括号（}}）AA、BB正确匹配呢？
如表达式1、用$kk ＝~ s/\{\{  ([^\}]+) \}\}/&Fuction($1)/gxe;  适合表达式1的情况但不适合表达式2的情况;
表达式2、用$kk ＝~ s/\{\{ (.*) \}\}/&Fuction($1)/gxe;  适合表达式2的情况但不适合表达式1的正确匹配；

与数学优先级高的小括号计算式表达式一样：
1、（2＋3）×（4－8）
2、5×（3＋8×（3＋4））
不知道计算机或者计算器是如何正确匹配计算式小括号配对的？？？
请大家多给建议或意见！
谢谢大家了！
minirain
20101023

zhlong8

再复杂也不过是个树，像lisp那样

minirain

再复杂也不过是个树，像lisp那样
zhlong8 发表于 2010-10-23 22:45

    请问如何实现呢？谢谢！

zhlong8

以前实现 scheme 的 read 的时候写个类似的。[current, parent] 这样的结构，遇到 '(' 就新加一层变成
[new_current, [current, parent]]，遇到 ')' 就消除一层……还要再具体吗

minirain

以前实现 scheme 的 read 的时候写个类似的。[current, parent] 这样的结构，遇到 '(' 就新加一层变成
[ne ...
zhlong8 发表于 2010-10-23 22:53

    能给个用PERL程序实现的例子，可以吗？

zhlong8

package T

1. package T;
   
2. 
   
3. use 5.012;
   
4. use warnings;
   
5. 
   
6. sub new {
   
7.     my($class, $parent) = @_;
   
8.     bless {
   
9.         current => [],
   
10.         parent => $parent
    
11.     }, $class;
    
12. }
    
13. 
    
14. sub dec {
    
15.     my $self = shift;
    
16.     push @{$self->{parent}{current}}, $self->{current};
    
17.     $self->{parent};
    
18. }
    
19. 
    
20. sub add {
    
21.     my($self, $val) = @_;
    
22.     push @{$self->{current}}, $val;
    
23. }
    
24. 
    
25. sub top {
    
26.     bless {current => [], parent=> []}, shift;
    
27. }
    
28. 
    
29. 1;
    

复制代码

实现

1. use 5.012;
   
2. use warnings;
   
3. use T;
   
4. use Data::Dumper;
   
5. use Regexp::Common;
   
6. 
   
7. sub parse {
   
8.     my $tree = T->top;
   
9.     for (@_) {
   
10.         given ($_) {
    
11.             when ('(') {$tree = T->new($tree)}
    
12.             when (')') {$tree = $tree->dec;}
    
13.             default {$tree->add($_);}
    
14.         }
    
15.     }
    
16.     say Dumper $tree;
    
17. }
    
18. 
    
19. sub tokenize {  #功能非常有限
    
20.     my $str = shift;
    
21.     say "got $str";
    
22.     my @all;
    
23.     while ($str =~ /\G\s*(\(|\)|$RE{num}{real}|$RE{num}{int}|\w+|[+\-*\/])\s*/g) {
    
24.         push @all, $1;
    
25.     }
    
26.     say "return @all";
    
27.     @all;
    
28. }
    
29. 
    
30. #(define a (+ 343 (* 3323 a)))
    
31. parse '(', 'define', 'a', '(', '+', '343', '(', '*', '3323', 'a', ')', ')', ')';
    
32. #或者
    
33. parse tokenize '(define a (+ 343 (* 3323 a)))'
    

复制代码

输出

1. $VAR1 = bless( {
   
2.                  'parent' => [],
   
3.                  'current' => [
   
4.                                 [
   
5.                                   'define',
   
6.                                   'a',
   
7.                                   [
   
8.                                     '+',
   
9.                                     '343',
   
10.                                     [
    
11.                                       '*',
    
12.                                       '3323',
    
13.                                       'a'
    
14.                                     ]
    
15.                                   ]
    
16.                                 ]
    
17.                               ]
    
18.                }, 'T' );
    

复制代码

有个Parse::RecDescent 模块，不过我不会用
还有 Regexp::Common::balanced

珞水的大叔

回复 1# minirain


    这个，单纯只用正则确实不容易啊，如果用堆栈的方式，可能会容易一些

zhlong8

回复 7# 珞水的大叔


    发现大叔太NB了，8月18到10月23总共65天在线855小时。
855/（65*24） ＝ 54.81%

珞水的大叔

回复 8# zhlong8


    嘿嘿嘿嘿……

toniz

貌似正则的话比较麻烦。

为了解析嵌套括号，如要完整取到括号信息，需要先把取到的括号变成其它字符，然后取出来后再变回去。

抛砖砸人，正则思路如下：

1. my $string = "0,0,{0,0},0,{50,50,50,50,{1,2},{3,4},0},0,{0,0}";
   
2. 1 while($string =~ s/\{([^{}]*)\}/print "$1\n";'$1';/ee);
   

复制代码

[etl@dmtest]$ perl tt.tt
0,0
1,2
3,4
50,50,50,50,1,2,3,4,0
0,0

这个是从内括号开始匹配，取出所有括号里面的信息，不足是外括号取内括号内容时候，会失去括号。

如果要做到完整提取，可以考虑用替换，把取出来后的括号替换成其它符号，获取之后再替换回去。

介绍下思路，具体的就不写啦