优先级和结合性的算法

104359176

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

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

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

复制代码

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

复制代码