优先级和结合性的算法

104359176

我以前感觉这个算法没什么用，现在想来，这个算法在语法树分析中，是非常必要的一种算法：

有若干个操作符，例如 +,  *, ^, 这三个操作符的优先级不同，结合性也不同，^ 是左结合的，而 +， * 则是右结合，当然左结合也行。现在悬赏算法，如果采纳的话，赠送 5000 积分，如果算法优秀，我相信会有人打赏的。

1. a + b * c ^ d => (a + (b * (c ^ d))

复制代码

rubyish

my brick.pl

1. #/usr/bin/perl
   
2. use 5.024;
   
3. 
   
4. my @op = qw[ + - * / ^ ~ ];
   
5. my @preass = ( [ 0, 0 ], [ 0, 0 ], [ 1, 0 ], [ 1, 0 ], [ 2, 1 ], [ 3, 1 ] );
   
6. my ( @it, @ass );
   
7. sub that;
   
8. 
   
9. for my $i ( 0 .. $#op ) {
   
10.     $it[ $preass[$i][0] ] .= "\\$op[$i]";
    
11.     $ass[ $preass[$i][0] ] //= $preass[$i][1];
    
12. }
    
13. 
    
14. @it = map qr/\s*([$_])\s*/, @it;
    
15. 
    
16. sub that {
    
17.     my ( $equ, $i ) = @_;
    
18.     return @$equ if $i > $#it;
    
19.    
    
20.     state $at   = [ 0, -3 ];
    
21.     state $join = [ [ 0 .. 2 ], [ -3 .. -1 ] ];
    
22.     local $|    = 1;
    
23.    
    
24.     my @one = map $|-- ? that [ split $it[$i] ], $i + 1 : $_, @$equ;
    
25.     my $ass = $ass[ $i - 1 ];
    
26.     my $pos = $at->[$ass];
    
27.     my $dit = $join->[$ass];
    
28. 
    
29.     splice @one, $pos, 3, "(@one[@$dit])" until @one == 1;
    
30.     @one;
    
31. }
    
32. 
    
33. sub this { that [shift], 0 }
    
34. 
    
35. while (<DATA>) {
    
36.     chomp;
    
37.     say $_, ' =>';
    
38.     say this $_;
    
39.     say '-' x 64;
    
40. }
    
41. 
    
42. __DATA__
    
43. 1+2+3+4+5
    
44. 1*2*3*4 * 5 + 6-7   /8
    
45. 1^2~3*4-5
    
46. 1/2/3/4/5*6*7^8^9-10-11*12
    
47. a + b * c ^ d + e - f * g / h ^ i ~ j
    
48. 3 ^ 4 ^ 5 ^ 6 - 7 / 8 + 9 ^ 10 ^ 11 * 12
    
49. 1 + 2 + 3 - 4 - 5 * 6 * 7 / 8 / 9 ^ 10 ^ 11 ~ 12 ~ 13 - 14
    
50. 1 - 2 ^ 3 ^ 4 + 5 * 6 / 7
    

复制代码

op:
1+2+3+4+5 =>
((((1 + 2) + 3) + 4) + 5)
----------------------------------------------------------------
1*2*3*4 * 5 + 6-7   /8 =>
((((((1 * 2) * 3) * 4) * 5) + 6) - (7 / )
----------------------------------------------------------------
1^2~3*4-5 =>
(((1 ^ (2 ~ 3)) * 4) - 5)
----------------------------------------------------------------
1/2/3/4/5*6*7^8^9-10-11*12 =>
((((((((1 / 2) / 3) / 4) / 5) * 6) * (7 ^ (8 ^ 9))) - 10) - (11 * 12))
----------------------------------------------------------------
a + b * c ^ d + e - f * g / h ^ i ~ j =>
(((a + (b * (c ^ d))) + e) - ((f * g) / (h ^ (i ~ j))))
----------------------------------------------------------------
3 ^ 4 ^ 5 ^ 6 - 7 / 8 + 9 ^ 10 ^ 11 * 12 =>
(((3 ^ (4 ^ (5 ^ 6))) - (7 / ) + ((9 ^ (10 ^ 11)) * 12))
----------------------------------------------------------------
1 + 2 + 3 - 4 - 5 * 6 * 7 / 8 / 9 ^ 10 ^ 11 ~ 12 ~ 13 - 14 =>
(((((1 + 2) + 3) - 4) - ((((5 * 6) * 7) / / (9 ^ (10 ^ (11 ~ (12 ~ 13)))))) - 14)
----------------------------------------------------------------
1 - 2 ^ 3 ^ 4 + 5 * 6 / 7 =>
((1 - (2 ^ (3 ^ 4))) + ((5 * 6) / 7))
----------------------------------------------------------------

sunzhiguolu

不懂, 帮顶

104359176

看样要抛砖引玉了。

这是一个利用模块的实现：

https://github.com/ingydotnet/pe ... ial/Calculator.swim

1. Consider the equation:
   
2. 
   
3.   1 - 2 ^ 3 ^ 4 + 5 * 6 / 7
   
4. 
   
5. Normal precedence and associativity rules make this the same as:
   
6. 
   
7.   (1 - (2 ^ (3 ^ 4)) + ((5 * 6) / 7))
   

复制代码

1. {
   
2.       package Calculator;
   
3.       use base 'Pegex::Tree', 'Precedence';
   
4. 
   
5.       my $operator_precedence_table = {
   
6.           '+' => {p => 1, a => 'l'},
   
7.           '-' => {p => 1, a => 'l'},
   
8.           '*' => {p => 2, a => 'l'},
   
9.           '/' => {p => 2, a => 'l'},
   
10.           '^' => {p => 3, a => 'r'},
    
11.       };
    
12. 
    
13.       sub got_expr {
    
14.           my ($self, $expr) = @_;
    
15.           $self->precedence_rpn($expr, $operator_precedence_table);
    
16.       }
    
17.   }

复制代码

hztj2005

前几年看过龙书的大部分内容，但很久不用，印象就模糊了。

如果楼主懂c，可以看Kenneth C.Louden 《编译原理及实践》，此书有一个C语言实现的完整代码，看懂之后改写成Perl，是比较可行的方法。

要想完全独立用perl的实现，即使这么简单的问题，可能要折腾好几天乃至更久的时间。

可以分解问题，先不考虑结合性，只考虑优先级。

实现中，有这种问题： 4+6^(3+2)-5，就是操作数不是一个单纯的数字，而是一个表达式(3+2)，需要递归实现。