優(yōu)先級(jí)和結(jié)合性的算法

104359176

我以前感覺這個(gè)算法沒什么用，現(xiàn)在想來(lái)，這個(gè)算法在語(yǔ)法樹分析中，是非常必要的一種算法：

有若干個(gè)操作符，例如 +,  *, ^, 這三個(gè)操作符的優(yōu)先級(jí)不同，結(jié)合性也不同，^ 是左結(jié)合的，而 +， * 則是右結(jié)合，當(dāng)然左結(jié)合也行�，F(xiàn)在懸賞算法，如果采納的話，贈(zèng)送 5000 積分，如果算法優(yōu)秀，我相信會(huì)有人打賞的。

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

復(fù)制代碼

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
    

復(fù)制代碼

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

看樣要拋磚引玉了。

這是一個(gè)利用模塊的實(shí)現(xiàn)：

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))
   

復(fù)制代碼

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.   }

復(fù)制代碼

hztj2005

前幾年看過(guò)龍書的大部分內(nèi)容，但很久不用，印象就模糊了。

如果樓主懂c，可以看Kenneth C.Louden 《編譯原理及實(shí)踐》，此書有一個(gè)C語(yǔ)言實(shí)現(xiàn)的完整代碼，看懂之后改寫成Perl，是比較可行的方法。

要想完全獨(dú)立用perl的實(shí)現(xiàn)，即使這么簡(jiǎn)單的問題，可能要折騰好幾天乃至更久的時(shí)間。

可以分解問題，先不考慮結(jié)合性，只考慮優(yōu)先級(jí)。

實(shí)現(xiàn)中，有這種問題： 4+6^(3+2)-5，就是操作數(shù)不是一個(gè)單純的數(shù)字，而是一個(gè)表達(dá)式(3+2)，需要遞歸實(shí)現(xiàn)。