Algorithm Needed

1. Senior Member
Join Date
Dec 1969
Posts
2,885

Algorithm Needed

Hey,<BR><BR>I am doing analysis for rewriting a module that we refer to as the "Math Editor". Basically, it looks like a calculator and is used to create a "Rule" to be used in a "Rules Engine". The expressions that can be created for the rule are special in the sense that the oprands can also include a field from a transaction record and/or some thing we refer to as a "Container Function".<BR><BR>A typical expression may look like:<BR>500 + (Table.Field * 100) / Container.Sum<BR><BR>The problem is this - the "rule" XML stores the expression as a data structure that mirrors Polish Notation [not Reverse Polish Notation]. It would be extremely easy for me to store the expression if the user would key the expression as if they were working in Polish Notation. However, I cannot convince the powers that be to train end users to do this. So....... I need an algorithm to take expressions that are keyed in sequence from left to right and track the expression so that I can either eventually or simultaneaously convert it to Polish Notation.<BR><BR>To get a better picture of the structure, look at the expression tree here: http://www7.brinkster.com/christophern/mdsve.htm<BR><BR>I posted this in the Advanced Forum because I doubt that anyone but Bill Wilkinson knows *** I am talking about. Thanks

2. Junior Member
Join Date
Dec 1969
Posts
5

RE: Algorithm Needed

So 500 + (Table.Field * 100) / Container.Sum should look like:<BR><BR>500 Container.Sum 100 Table.Field * / +<BR><BR>I guess you need to parse for "(" then ")" grabbing the in between. You will need to run 2 strings for the vars, and the operands. Then combine the strings, or just gen the XML.<BR><BR>HTH<BR><BR>__Stephen

3. Senior Member
Join Date
Dec 1969
Posts
2,885

RE: Algorithm Needed

That is the way it works now. We want to move away from parsing strings: the expressions can become fairly complex and heavily nested. It is hard to recognize operands, given the unusual nature or the viable operand types. What I really need is to track operands, operator, and sub expressions AS THEY ARE ENTERED, and not after the fact [an expression as a whole]. Thanks.

4. Senior Member
Join Date
Dec 1969
Posts
2,885

ATTN: Bill Wilkinson

Hey Bill,<BR><BR>I have heard you talk about RPN on here. Any ideas about my problem???

5. Senior Member
Join Date
Dec 1969
Posts
96,118

Well, if my handheld calculator...

...can do this, you *should* be able to do it.<BR><BR>But "forward" Polish Notation??? Ugh.<BR><BR>That&#039;s not efficient to process, let alone produce.<BR><BR>Hmmm...but I wonder...I&#039;ve never played with forward Polish, but I wonder if you can just reverse Reverse Polish???<BR><BR>My brain hurts.<BR><BR>Actually, if you think about it, when you parse a string to convert it to RPN, you never backtrack, do you? So what&#039;s the difference between that and just parsing the stuff as it is entered? I don&#039;t see a logical difference here.<BR><BR>I gotta run for now...back later.<BR><BR>

6. Senior Member
Join Date
Dec 1969
Posts
96,118

How about a sample?

Of a few expressions that have been converted to forward Polish that is acceptable to that system?<BR><BR>I want a sanity check on my notion that we can simply reverse the RPN.<BR><BR>

7. Senior Member
Join Date
Dec 1969
Posts
2,885

RE: How about a sample?

Hey Bill,<BR><BR>I do not know if strict Polish Notation is what I am after, or some version thereof, of something that I am making up. Basically, I need to have expressions ordered as:<BR>Operator, Oprand1, Operand2, .... OperandN<BR>If any of the operands are a sub-expression, then the process starts again. <BR><BR>For this expression:<BR>( Accrued Interest from the Financial (IP) Datasource * .05 ) - Fee from the Financial (IP) Datasource<BR><BR>The end result will be an XML structure like this:<BR>&#060;DSV_EXPRESSION&#062;<BR>&#060;TYPE& #062;MATH&#060;/TYPE&#062;<BR>&#060;OPERATOR&#062;MINUS&#060;/OPERATOR&#062;<BR>&#060;OPERANDS&#062;<BR>&#060;DS V_EXPRESSION&#062;<BR>&#060;TYPE&#062;MATH&#060;/TYPE&#062;<BR>&#060;OPERATOR&#062;TIMES&#060;/OPERATOR&#062;<BR>&#060;OPERANDS&#062;<BR>&#060;DS V&#062;<BR>&#060;DATASOURCE&#062;<BR>&#060;NAME&#0 62;Financial&#060;/NAME&#062;<BR>&#060;FIELD&#062;accrued_interest&#0 60;/FIELD&#062;<BR>&#060;/DATASOURCE&#062;<BR>&#060;/DSV&#062;<BR>&#060;DSV&#062;<BR>&#060;LITERAL&#062 ;<BR>&#060;DATA_TYPE&#062;UNDEF&#060;/DATA_TYPE&#062;<BR>&#060;VALUE&#062;.05&#060;/VALUE&#062;<BR>&#060;/LITERAL&#062;<BR>&#060;/DSV&#062;<BR>&#060;/OPERANDS&#062;<BR>&#060;/DSV_EXPRESSION&#062;<BR>&#060;DSV&#062;<BR>&#060;D ATASOURCE&#062;<BR>&#060;NAME&#062;Financial&#060;/NAME&#062;<BR>&#060;FIELD&#062;fee&#060;/FIELD&#062;<BR>&#060;/DATASOURCE&#062;<BR>&#060;/DSV&#062;<BR>&#060;/OPERANDS&#062;<BR>&#060;/DSV_EXPRESSION&#062;<BR>

8. Senior Member
Join Date
Dec 1969
Posts
96,118

Ugh. That's really ugly XML!

Just for example, it should be<BR><BR>&#060;DSV_EXPRESSION Type="MATH"&#062;<BR>&#060;OPERATOR Type="MINUS" /&#062;<BR>...<BR>&#060;DATASOURCE Name="Financial" Field="accrued_interest" /&#062;<BR>&#060;LITERAL Data_Type="UNDEF" Value="0.05" /&#062;<BR><BR>etc.<BR><BR>In fact, I wonder if &#060;DSV&#062; could be "folded in", as well.<BR><BR><BR>It&#039;s purely silly for OPERATOR and LITERAL to be done other than that, and I *suspect* that is true of DSV_EXPRESSION and DATASOURCE as well (can&#039;t tell from the limited example).<BR><BR>Let&#039;s see....<BR><BR>So in more readable notation, that becomes:<BR> - * [Financial.accrued_interest] [0.05] [Financial.fee]<BR><BR>And in RPN it would be<BR> [Financial.accrued_interest] [0.05] * [Financial.fee] -<BR><BR>Ugh. So PN is not simply RPN reversed. Double ugh.<BR><BR>I&#039;ve never written code to generate PN, I&#039;m afraid. Not instantly clear to me how to do so.<BR><BR>This simple example makes it appear that you would simply pre-pend the operator to the front of the sequence, instead of dropping it "in place" as you do with RPN, but I&#039;m not convinced that&#039;s true of more complex expressions.<BR><BR>Have anything reasonably complex that can give a better example?<BR><BR><BR><BR>

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•