August 3, 2011 at 9:46 am
I have for my project a (large, several thousands already and growing) set of expressions, stored as numbered tokens ordered in infix notation. For a very important part of the system these tokens need to be re-ordered into Reverse Polish Notation (RPN).
An algorithm to go from Infix into RPN has been published by Edgser Dijkstra, the "Shunting-yard algorithm". It is described here: http://en.wikipedia.org/wiki/Shunting-yard_algorithm. I need an implemention of this algorithm (or an alternative?) in T-SQL for SQL server 2008 R2.
To illustrate the problem, here's 2 sets of query output: one the way I have it and one they way I would like to get it:
-- output before conversion:
--exprID Expression
------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--1 a.col1 = b.col1
--2 a.col1 = b.col1 AND a.col2 = b.col3
--3 a.col1 = b.col1 AND a.col2 = b.col3 AND a.col4 = b.col4
--(3 row(s) affected)
-- Needed output AFTER conversion:
--exprID Expression
------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--1 a.col1 b.col1 =
--2 a.col1 b.col1 = a.col2 b.col3 = AND
--3 a.col1 b.col1 = a.col2 b.col3 = a.col4 b.col4 = AND AND
--(3 row(s) affected)
I've written a test script, having both the DDL and some test data to experiment with. This script is in the attached zip file.
My problem is in the fact that the algorithm relies heavily on a stack and I can't think of a way to properly implement this in cte's. I hope that someone can give me some pointers on how to do this or better yet, that someone encountered this or a similar problem before and is willing to share their findings!
Thanks very much!
Richard
August 3, 2011 at 1:49 pm
Why not this? And enabling shortcurcuit?
--3 a.col1 b.col1 = a.col2 b.col3 = AND a.col4 b.col4 = AND
N 56°04'39.16"
E 12°55'05.25"
August 3, 2011 at 5:41 pm
Hi SwePeso,
Thanks for the response, but I don't yet see how that helps me?
I think it doesn't help me because your RPN representation is not exactly the same expression any more as the original in infix notation. The routines that I need to feed the expressions into expect them to be in RPN, whereas one of the sources that the expressions come from, delivers them in infix notation. I agree, the net result is probably the same for my example expressions. But we have, next to the simple cases, more complex expressions with ORs and all sorts of other operators in them. These will get different semantics if we would re-arrange operators like you propose.
Having the expressions in RPN (or PN, which is simply RPN read backwards) ensures we don't need any brackets to specify the expressions unambiguously. This makes parsing, interpreting and manipulating the expressions a lot easier and faster. For a large set of expressions we've already got them in RPN, but now I've hit a source of expressions that only delivers them in infix order so I need these properly re-ordered. I've found this algorithm that is said to do it, but I can't think of a way to implement the stack part of that algorithm in a cte.
I think your response is aimed at getting an optimal performance when evaluating the example expression, not at how to convert infix into RPN. Or am I totally missing the point in your response?
August 3, 2011 at 9:41 pm
I am just trying to establish if you want a certain dialect of RPN or not.
My suggested statement is a valid RPN notation and will create the same result as yours.
With the difference that my suggestion can be shortcircuit if the parser is smart enough; due the earlier AND condition. If the two stack values are not the same at the earlier point, there is no need to continue to the second AND. My suggestion is also optimized to handle fewer stack values.
N 56°04'39.16"
E 12°55'05.25"
August 3, 2011 at 10:31 pm
I am not completely sure yet that I understand you correctly. Are you saying that there is another algorithm, producing slightly different RPN expressions -but still valid RPN-, which evaluate to the exact same result as the original infix expression just like Dijkstra's algorithm? And that this algorithm will work for any type of input infix expression, just like Dijkstra's algorithm? And this algorithm can be implemented in a T-SQL cte? Because if you do, then YES, that is very welcome!
I have manually processed your example back into the original infix expression to verify that they are the same and do indeed not see a difference. Therefor I don't expect any difficulties if I would produce the RPN your way. I could not get the job done yet using Dijkstra's algorithm. So please point me to a description of your alternative algorithm! :w00t:
August 4, 2011 at 12:03 am
Let's see this in a "stack view".
--1 a.col1 = b.col1
--2 a.col1 = b.col1 AND a.col2 = b.col3
--3 a.col1 = b.col1 AND a.col2 = b.col3 AND a.col4 = b.col4
--1 a.col1 = b.col1 -- 1 2 3
--2 a.col1 = b.col1 AND a.col2 = b.col3 -- 1 2 3 4 5 6 7
--3 a.col1 = b.col1 AND a.col2 = b.col3 AND a.col4 = b.col4 -- 1 2 3 4 5 6 7 8 9 10 11
And the result you want is something like this
--1 a.col1 b.col1 =
--2 a.col1 b.col1 = a.col2 b.col3 = AND
--3 a.col1 b.col1 = a.col2 b.col3 = AND a.col4 b.col4 = AND
--1 a.col1 b.col1 = -- 1 3 2
--2 a.col1 b.col1 = a.col2 b.col3 = AND -- 1 3 2 5 7 6 4
--3 a.col1 b.col1 = a.col2 b.col3 = AND a.col4 b.col4 = AND -- 1 3 2 5 7 6 4 9 11 10 8
And as you can see now, there is a pattern!
5-7-6-4 and 9-11-10-8 which is {p, p+2, p+1, p-1}
Now, is this also true for the first comparison, 1 3 2 ?
Yes. 1 3 2 is the same {p, p+2, p+1, p-1}. However, since p-1 is equal to zero, this position is not displayed!
If you also have OR in the algorithm, you simply put that on stack and evaluate the other "leg" first.
The importance of this pattern is that you could take a splitfunction and split with space.
Then rearrange the items according to the pattern discovered above and concatenate the string afterwards.
N 56°04'39.16"
E 12°55'05.25"
August 4, 2011 at 12:19 am
Here is one algorithm to get the correct pattern
SELECTv.Number,
f.Position
FROMmaster.dbo.spt_values AS v
CROSS APPLY(
VALUES(0, 4 * v.Number - 3),
(1, 4 * v.Number - 1),
(2, 4 * v.Number - 2),
(3, 4 * v.Number - 4)
) AS f(RowID, Position)
WHEREv.Type = 'P'
AND v.Number BETWEEN 1 AND 15
AND f.Position > 0
ORDER BYv.Number,
f.RowID
N 56°04'39.16"
E 12°55'05.25"
August 4, 2011 at 2:18 am
Thanks a lot Peso, I'll have a look at your "pattern-approach". My initial impression though is that it will not work when we encounter other expressions like for example a.col1 = b.col1 and not a.col2 is null. Is that right?
In the mean time I had gone ahead already with a procedural approach. Below is what I came up with. It doesn't have support for parenthesis nor functions as was described in the wiki page. Functions I won't need for now and support for parenthesis are easily added (but I hadn't anticipated for them in the example script). Now at least I've got something that fulfills my need of delivering the RPN expressions.
Again, Thank you very much for your help. If you want me to I can let you know what I did with it in a week or so.
One more question still on your idea for the short-circuit optimization: I see what you are doing, but how can I automate it? Do you have any suggestions on how I can have the program detect these situations?
create function dbo.fnConvertInfixToRPN(
@ExprID int
)
returns @RPN table (
SequenceNB int not null
,TokenID int not null
,primary key (SequenceNB)
)
as
begin
declare @Stack table (
ID int identity(1,1) not null -- I don't care about the absolute value of this ID,
-- I just need every new value inserted to have a value
-- greater than any previously inserted value.
,TokenID int not null
,Precedence int null
,primary key clustered (ID)
);
declare @SequenceNB int;
declare @TokenID int;
declare @TokenID2 int;
declare @Associativity char(1);
declare @Precedence int;
declare @Rows int;
declare cur cursor local fast_forward
for
select i.TokenID
from dbo.InfixSequences i
where i.ExprID = @ExprID
order by i.SequenceNB;
open cur;
select @SequenceNB = 1;
while 1 = 1
begin
fetch next from cur into @TokenID;
if @@fetch_status = -1
break;
if @@fetch_status = 0
begin
-- If the token is an attribute, add it to the output.
insert @RPN(SequenceNB, TokenID)
select @SequenceNB, @TokenID
from dbo.Attributes att
where att.TokenID = @TokenID;
select @Rows = @@rowcount;
if @Rows > 0
begin
select @SequenceNB += 1;
continue;
end
select @Associativity = op.Associativity
,@Precedence = op.Precedence
from dbo.Operators op
where op.TokenID = @TokenID;
select @Rows = @@rowcount;
if @Rows > 0
begin
-- While there is an operator token O2 at the top of the stack,
-- and either:
-- O1 is left associative and its precendence
-- is greater than or equal to that of O2,
-- Or, O1 is right associative and its precedence is greater
-- than that of O2.
-- Pop O2 off the stack, onto the output.
while 1 = 1
begin
select @TokenID2 = t.TokenID
from (
select row_number() over (order by s.ID desc) as pos
,s.Precedence
,s.TokenID
from @Stack s
) t
where t.pos = 1
and t.Precedence is not null -- is an operator, not a parenthesis.
and (@Precedence > t.Precedence or (@Precedence = t.Precedence and @Associativity = 'L'));
select @Rows = @@rowcount;
if not @Rows > 0
break;
insert @RPN(SequenceNB, TokenID)
values(@SequenceNB, @TokenID2);
select @SequenceNB += @Rows;
delete
from @Stack
where ID = (select max(ID) from @Stack)
end
-- Push O1 onto the stack.
insert @Stack(TokenID, Precedence)
values( @TokenID, @Precedence);
continue;
end
-- If the token is left parenthesis, then push it onto the stack.
if @TokenID = -1
begin
insert @Stack(TokenID)
values( @TokenID);
continue;
end
-- If the token is right parenthesis:
-- - If the stack runs out without finding a left parenthesis, then there are mismatched parenthesis.
if @TokenID = -2
begin
-- - Until the token at the top of the stack is a left parenthesis,
while 1 = 1
begin
select
@TokenID2 = t.TokenID
from (
select row_number() over (order by s.ID desc) as pos
,s.Precedence
,s.TokenID
from @Stack s
) t
where t.pos = 1;
select @Rows = @@rowcount;
if not @Rows > 0
begin
break; -- ERROR, mismatched parenthesis!
end
-- N/A: no support for functions yet.
if @TokenID2 = -1
begin
-- Pop the left parenthesis off the stack, but not onto the output.
delete
from @Stack
where ID = (select max(ID) from @Stack)
break;
end
-- pop operators O2 off the stack, onto the output.
insert @RPN(SequenceNB, TokenID)
values(@SequenceNB, @TokenID2);
select @SequenceNB += 1;
delete
from @Stack
where ID = (select max(ID) from @Stack)
end
continue;
end
end
end
close cur;
deallocate cur;
insert @RPN(SequenceNB, TokenID)
select (@SequenceNB - 1) + row_number() over (order by s.ID desc), s.TokenID
from @Stack s;
return;
end
go
-- See the sequences generated:
select t.exprID, fn.SequenceNB, fn.TokenID
from (
select ExprID
from dbo.InfixSequences
group by ExprID
) t
cross apply dbo.fnConvertInfixToRPN(t.ExprID) fn
order by 1, 2, 3
-- Or in a more human readable format:
with cteExpressionIDs as (
select i.ExprId
from dbo.InfixSequences i
group by i.ExprID
)
select e.exprID
,stuff((
select N' ' + isnull(att.Name, op.Token) as [text()]
from dbo.fnConvertInfixToRPN(e.ExprID) fn
left outer join dbo.Attributes att on (att.TokenID = fn.TokenID)
left outer join dbo.Operators op on (op.TokenID = fn.TokenID)
order by fn.SequenceNB
for xml path(''),type
).value('.','nvarchar(max)'), 1, 1, '') as Expression
from cteExpressionIDs e;
"Human readable" results before and after conversion are:
exprID Expression
----------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 a.col1 = b.col1
2 a.col1 = b.col1 AND a.col2 = b.col3
3 a.col1 = b.col1 AND a.col2 = b.col3 AND a.col4 = b.col4
4 NOT a.col1 = b.col1
5 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
exprID Expression
----------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 a.col1 b.col1 =
2 a.col1 b.col1 = a.col2 b.col3 = AND
3 a.col1 b.col1 = a.col2 b.col3 = AND a.col4 b.col4 = AND
4 a.col1 b.col1 = NOT
5 3 4 2 * 1 5 - 2 3 ^ ^ / +
August 4, 2011 at 5:04 am
Hi SwePeso,
Unless something drastic happens, this will be my last posting in this topic. I found and fixed a bug in the precedence detection and to my surprise your "short-circuit optimized" version was the result! :hehe: i.e. my initial 'needed output' was wrong to begin with... Furthermore I added support for parenthesis, plus some more test expressions. Among which the one from the wiki page, to show it all works correct now.
I've update the code and output in my previous posting to show only the correct version for anyone who may need it in the future.
Viewing 9 posts - 1 through 8 (of 8 total)
You must be logged in to reply to this topic. Login to reply