各位大虾，小弟有难啊！

rubyish

回复 39# MMMIX

精彩~ 先收藏，再慢慢研究，谢谢了。

   

Monox

有人帖语法分析解决这个问题的Perl代码了，我的初衷就达到了。不过我自己决定了自己要写的，当然说了有人帖Perl代码的话我多半就不会去尝试用Perl实现了。我用Haskell的尝试已经写完了（Haskell的parserc库果然很适合做这种工作，以致于我都不打算再用其它方式实现了，所以我只提供这一份代码），首先演示编译和执行过程：

1. $cabal build
   
2. Building sym-0.1.0.0...
   
3. Preprocessing executable 'sym' for sym-0.1.0.0...
   
4. [1 of 3] Compiling Sym.SyntaxTree   ( src/Sym/SyntaxTree.hs, dist/build/sym/sym-tmp/Sym/SyntaxTree.o )
   
5. [2 of 3] Compiling Sym.Parser       ( src/Sym/Parser.hs, dist/build/sym/sym-tmp/Sym/Parser.o )
   
6. [3 of 3] Compiling Main             ( src/sym.hs, dist/build/sym/sym-tmp/Main.o ) [Sym.Parser changed]
   
7. Linking dist/build/sym/sym ...
   
8. $ dist/build/sym/sym
   
9. > (A interact ((B or C) or (((D inside E) or F) inside G)))
   
10. ["A_B","A_C","A_D_E_G","A_F_G"]
    
11. > (A interact ((B or C) or (((D inside E) or F) not inside G)))
    
12. ["A_B","A_C","A_D_E","A_F"]
    
13. >
    

复制代码

如上面的输出，我这个做的是交互方式解析，要改成从文件读取也是很容易的，另外我使用了字符串列表的方式进行输出，改变输出方式也是很容易实现的。最后要说明的一点是因为我只是随便尝试一下解决这个问题，所以为了处理的方便，not 和 inside 之前有且只能有一个空格。下面是代码：
LICENSE 文件略去
Setup.hs:

1. import Distribution.Simple
   
2. main = defaultMain

复制代码

sym.cabal:

1. name:                sym
   
2. version:             0.1.0.0
   
3. synopsis:            A toy symbol manipulation tool.
   
4. description:         A toy symbol manipulation tool.
   
5. homepage:            https://github.com/qiuhw/sym
   
6. license:             BSD3
   
7. license-file:        LICENSE
   
8. author:              Hongwen Qiu
   
9. maintainer:          qiuhongwen@gmail.com
   
10. copyright:           2013 Hongwen Qiu
    
11. category:            Compiler
    
12. build-type:          Simple
    
13. cabal-version:       >=1.8
    
14. 
    
15. executable sym
    
16.   main-is:           sym.hs
    
17.   other-modules:     Sym.SyntaxTree
    
18.                      Sym.Parser
    
19.   hs-source-dirs:    src
    
20.   build-depends:     base ==4.6.*,
    
21.                      containers ==0.5.*,
    
22.                      mtl ==2.1.*,
    
23.                      parsec ==3.1.*
    

复制代码

src/sym.hs:

1. import System.IO (BufferMode(..), hSetBuffering, putStr, stdout)
   
2. import System.IO.Error (catchIOError)
   
3. 
   
4. import Sym.SyntaxTree (Expr(..), evalExpr)
   
5. import Sym.Parser (parseStmt)
   
6. 
   
7. main = do
   
8.     hSetBuffering stdout NoBuffering
   
9.     mainLoop
   
10. 
    
11. mainLoop :: IO ()
    
12. mainLoop = do
    
13.     putStr "> "
    
14.     catchIOError (getLine >>= mainLoop') (\_ -> return ())
    
15. 
    
16. mainLoop' :: String -> IO ()
    
17. mainLoop' s = do
    
18.     case parseStmt s of
    
19.         Left e     -> print e
    
20.         Right expr -> print $ evalExpr expr
    
21.     mainLoop
    

复制代码

src/Sym/Parser.hs:

1. 
   
2. module Sym.Parser (parseStmt) where
   
3. 
   
4. import Control.Monad (liftM)
   
5. import Text.Parsec (ParseError, (<|>), (<?>), parse)
   
6. import Text.Parsec.Expr (Assoc(..), Operator(..), buildExpressionParser)
   
7. import qualified Text.Parsec.Token as Parsec
   
8. import Text.Parsec.Language (haskellStyle)
   
9. 
   
10. import Sym.SyntaxTree (Expr(..))
    
11. 
    
12. parseStmt :: String -> Either ParseError Expr
    
13. parseStmt = parse expr "(unknown)"
    
14. 
    
15. expr =  buildExpressionParser table term
    
16.     <?> "expression"
    
17. 
    
18. term =  parens expr
    
19.     <|> liftM ID identifier
    
20.     <?> "simple expression"
    
21. 
    
22. table = [ [binary "not inside" Not AssocLeft]
    
23.         , [binary "interact" And AssocLeft, binary "inside" And AssocLeft]
    
24.         , [binary "or" Or AssocLeft]
    
25.         ]
    
26. 
    
27. prefix  name fun = Prefix  (reservedOp name >> return fun )
    
28. postfix name fun = Postfix (reservedOp name >> return fun)
    
29. binary  name fun = Infix   (reservedOp name >> return fun )
    
30. 
    
31. lexer = Parsec.makeTokenParser haskellStyle
    
32. 
    
33. parens     = Parsec.parens lexer
    
34. identifier = Parsec.identifier lexer
    
35. reservedOp = Parsec.reservedOp lexer
    

复制代码

src/Sym/SyntaxTree.hs:

1. module Sym.SyntaxTree
   
2.     ( Expr(..)
   
3.     , evalExpr
   
4.     ) where
   
5. 
   
6. data Expr = ID String
   
7.           | And Expr Expr
   
8.           | Or Expr Expr
   
9.           | Not Expr Expr
   
10. 
    
11. instance Show Expr where
    
12.     show (ID  s)     = s
    
13.     show (And e1 e2) = parens e1 ++ " interact " ++ parens e2
    
14.     show (Or  e1 e2) = parens e1 ++ " or " ++ parens e2
    
15.     show (Not e1 e2) = parens e1 ++ " not inside " ++ parens e2
    
16. 
    
17. parens (ID s) = s
    
18. parens e      = '(' : show e ++ ")"
    
19. 
    
20. evalExpr :: Expr -> [String]
    
21. evalExpr (ID s) = [s]
    
22. 
    
23. evalExpr (And e1 e2) = zipWith (\h t -> h ++ "_" ++ t) head' tail'
    
24.   where head  = evalExpr e1
    
25.         tail  = evalExpr e2
    
26.         head' = concatMap (replicate (length tail)) head
    
27.         tail' = concat $ replicate (length head) tail
    
28. 
    
29. evalExpr (Or e1 e2) = evalExpr e1 ++ evalExpr e2
    
30. 
    
31. evalExpr (Not e1 _) = evalExpr e1
    

复制代码

yuanquan08

回复 42# Monox
精彩啊！！！
崇拜！！！

   

felonwan

yuanquan08 发表于 2013-12-20 13:08
我想对一个带括号的字符串解析，可是总得不到想要的结果：

t  = （A interact  ((B  or  C)  or (((D in ...

更新了“19楼”的perl脚本，加了测试的例子，这次是完整的。

算法：
循环地这样做：删除不必要的成对括号，匹配第一个“(...a+b...)*C”或“A*(...b+c...)”这样的模式，然后展开。

“(...a+b...)*C”和“A*(...b+c...)”中的括号里面再不含括号，是可以使用分配律的基本单元，而A和C则可以是单个变量或一对括号包括的一个块。
A和C的匹配用到了递归正则表达式。

哈，才发现楼主的东西比我想的加法和乘法运算还要简单，每两个变量运算后都加了括号，不会出现像（A or B or C）、(A inside B or C)等这样的类似情况。。。

felonwan

下面是我画的多项式展开流程图，不采用语法树算法，采用循环处理基本单元的方法，每次循环对基本括号（里面不含括号的括号）进行去括号或乘法分配。

rubyish

回复 45# felonwan

崇拜！{:3_188:}
   

felonwan

rubyish 发表于 2013-12-26 00:39
回复 45# felonwan

崇拜！

一直看不懂大神的那个代码，能不能给点解释哦？

yuanquan08

回复 46# rubyish
我也希望能解释一下，因为我也没有完全理解。

   

rubyish

回复 47# felonwan
回复 48# yuanquan08

版主 zhlong8 发表于 6楼:

1. 先把你这个字符串转换成结构化的数据，再想办法找出所有组合。
   
2. 第一步即使不会用正则表达式的方法也可以先分割字符，再用栈组合起来。
   
3. 第二步就是个递归。

复制代码

code:

1. #!/usr/bin/perl
   
2. 
   
3. # 先把你这个字符串转换成结构化的数据
   
4. sub From {
   
5.     map { s/(\w+)/'$1',/g; s/\(/[/g; s/\)/],/g; eval } shift;
   
6. }
   
7. 
   
8. # 想办法找出所有组合
   
9. sub SOp_eq_inxx__p {
   
10.     map join( '_', split /\|/ ),
    
11.       glob '{' . join( '}{', map join( '|,', @$_ ) . '|', @_ ) . '}';
    
12. }
    
13. 
    
14. # 就是个递归
    
15. sub Extract {
    
16.     my ( $Op, @data ) = @{ +shift }[ 1, 0, 2 ];
    
17.     $Op eq 'not' ? map { ref $_ ? Extract($_)     : $_   } $data[0] :
    
18.     $Op eq 'or'  ? map { ref $_ ? Extract($_)     : $_   } @data    :
    
19.     SOp_eq_inxx__p map { ref $_ ? [ Extract($_) ] : [$_] } @data    ;
    
20. }
    
21. 
    
22. my $String = <DATA>;
    
23. my @Result = Extract From $String;
    
24. print $_ . $/ for @Result;
    
25. 
    
26. __DATA__
    
27. (A interact  ((B  or  C)  or (((D inside E) or F)   not   inside G)))

复制代码

build-in function: join, split, glob, map, shift, eval, eq, ref
perldoc -f X

# sub SOp_eq_inxx__p == sub sop_eq_inxx__p

1. sub sop_eq_inxx__p {
   
2.     my ( $head, $tail ) = qw[{ }];
   
3.     my @param = @_;
   
4.     my @body  = map { join( '|,', @$_ ) . '|' } @param;
   
5.     my $body  = join $tail . $head , @body;
   
6.     my @all   = glob $head . $body . $tail;
   
7.     my @ret   = map { join '_', split /\|/, $_ } @all;
   
8.     return @ret;
   
9. }

复制代码

# sop_eq_inxx__p: usage

1. my @a = sop_eq_inxx__p [1], [ 2, 3, 4 ];
   
2. say join '|', @a;    # 1_2|1_3|1_4
   
3. my @b = sop_eq_inxx__p [ 1, 2 ], [ 3, 4 ];
   
4. say join '|', @b;    # 1_3|1_4|2_3|2_4
   
5. my @c = sop_eq_inxx__p [ 1, 2 ], [3];
   
6. say join '|', @c;    # 1_3|2_3

复制代码

# sub from == sub From

1. sub from {
   
2.     my $s = shift;
   
3.     $s    =~ s/(\w+)/'$1',/g;
   
4.     $s    =~ s/\(/[/g;
   
5.     $s    =~ s/\)/],/g;
   
6.     my $arrayref = eval $s;
   
7.     return $arrayref;
   
8. }

复制代码

# usage:

1. sub f1 {
   
2.     my $s = shift;
   
3.     $s    =~ s/(\w+)/'$1',/g;
   
4.     $s    =~ s/\(/[/g;
   
5.     $s    =~ s/\)/],/g;
   
6.     return $s;
   
7. }
   
8. 
   
9. 
   
10. my $s1 = '(1 2 3)';
    
11. say f1 $s1;           # ['1', '2', '3',],
    
12. my $arrayref = from $s1;    # $arrayref is an array-reference: [ 1, 2, 3 ]

复制代码

# sub Extract == sub extract

1. sub extract {
   
2.     my $p = shift;
   
3.     my @p = @$p;
   
4.     my ( $Op, @data ) = @p[ 1, 0, 2 ]; # $p[1] : or, not, inX
   
5.     if ( $Op eq 'not' ) {
   
6.         my $data = shift @data;
   
7.         if ( ref $data ) {
   
8.             return extract($data);
   
9.         }
   
10.         else { return $data }
    
11.     }
    
12.     elsif ( $Op eq 'or' ) {
    
13.         my @return;
    
14.         for (@data) {
    
15.             if ( ref $_ ) {
    
16.                 push @return, extract($_);
    
17.             }
    
18.             else { push @return, $_ }
    
19.         }
    
20.         return @return;
    
21.     }
    
22.     else {
    
23.         my @return = @data;
    
24.         for (@return) {
    
25.             if ( ref $_ ) {
    
26.                 $_ = [ extract($_) ];
    
27.             }
    
28.             else { $_ = [$_] }
    
29.         }
    
30.         @return = sop_eq_inxx__p( @return );
    
31.         return @return;
    
32.     }
    
33. }
    

复制代码

1. my $string = <DATA>;
   
2. my @result = extract from $string;
   
3. print $_ . $/ for @result;
   
4. __DATA__
   
5. (A interact  ((B  or  C)  or (((D inside E) or F)   not   inside G)))

复制代码

104359176

这个问题是什么意思，t0 t1 t2 是什么情况下？A B C D 这些参数是固定的吗？