Thread overview | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
August 16, 2012 How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Is there a simple function to create an operator tree of a term? For example: Term: 4 + 5 * 8 Tree: [*, 5, 8, +, 4] Or: Term: 2 * 2 + 2: Tree: [*, 2, 2, +, 2] |
August 16, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On Thursday, 16 August 2012 at 22:05:44 UTC, Namespace wrote: > Is there a simple function to create an operator tree of a term? > > For example: > Term: 4 + 5 * 8 > Tree: > [*, 5, 8, +, 4] > > Or: > Term: 2 * 2 + 2: > Tree: [*, 2, 2, +, 2] That seems to work: http://dpaste.dzfl.pl/95dccfa4 But it's more of a quick and dirty solution of me. Does anyone know, how can i do it more elegant? P.S.: Exists such "Diff" function as i used there in the standard library? I think something like that would be very useful. |
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On 17-Aug-12 03:41, Namespace wrote: > On Thursday, 16 August 2012 at 22:05:44 UTC, Namespace wrote: >> Is there a simple function to create an operator tree of a term? >> >> For example: >> Term: 4 + 5 * 8 >> Tree: >> [*, 5, 8, +, 4] >> >> Or: >> Term: 2 * 2 + 2: >> Tree: [*, 2, 2, +, 2] I do suspect you want Polish notation (and it does describe tree). Though in this respect the above is equivalent to + * 2 2 2 > > That seems to work: http://dpaste.dzfl.pl/95dccfa4 > But it's more of a quick and dirty solution of me. Does anyone know, how > can i do it more elegant? Wait, wait, wait. regex is not the ultimate answer put it aside for a moment please :) What you need is a proper operator precedence parser: http://en.wikipedia.org/wiki/Shunting-yard_algorithm or even simpler recursive descent parser. > > P.S.: Exists such "Diff" function as i used there in the standard > library? I think something like that would be very useful. -- Olshansky Dmitry |
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | o_O I was hoping that there is a shorter way than this. |
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On 17-Aug-12 12:38, Namespace wrote: > o_O > I was hoping that there is a shorter way than this. In short - sure thing there is, but if you want arbitrarily deep nested parenthesis then no. -- Olshansky Dmitry |
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Namespace | On 08/17/2012 10:38 AM, Namespace wrote: > o_O > I was hoping that there is a shorter way than this. I hacked together the following little parser (not extensively tested). http://dpaste.dzfl.pl/e616692e It transforms the input expression into polish notation, ignoring space characters. Note that it is significantly shorter than the regex attempt. It handles numbers, unary +, -, binary +, -, *, /, ^, where ^ associates to the right, as well as nested parentheses. It should be trivial to extend. (in this case you might want to generate the switch cases automatically from the operator precedence table.) |
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 08/17/2012 02:55 PM, Timon Gehr wrote:
> On 08/17/2012 10:38 AM, Namespace wrote:
>> o_O
>> I was hoping that there is a shorter way than this.
>
> I hacked together the following little parser (not extensively tested).
>
> http://dpaste.dzfl.pl/e616692e
>
> It transforms the input expression into polish notation, ignoring space
> characters.
> Note that it is significantly shorter than the regex attempt.
>
> It handles numbers, unary +, -, binary +, -, *, /, ^, where ^
> associates to the right, as well as nested parentheses. It should be
> trivial to extend. (in this case you might want to generate the switch
> cases automatically from the operator precedence table.)
(the first while loop is superfluous)
|
August 17, 2012 Re: How create a operator tree? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On Friday, 17 August 2012 at 12:55:24 UTC, Timon Gehr wrote:
> On 08/17/2012 10:38 AM, Namespace wrote:
>> o_O
>> I was hoping that there is a shorter way than this.
>
> I hacked together the following little parser (not extensively tested).
>
> http://dpaste.dzfl.pl/e616692e
>
> It transforms the input expression into polish notation, ignoring space
> characters.
> Note that it is significantly shorter than the regex attempt.
>
> It handles numbers, unary +, -, binary +, -, *, /, ^, where ^
> associates to the right, as well as nested parentheses. It should be
> trivial to extend. (in this case you might want to generate the switch
> cases automatically from the operator precedence table.)
Genial. Exactly what I'm looking for. Thanks!
|
Copyright © 1999-2021 by the D Language Foundation