Solution to TSQL Challenge 48 - Parse and evaluate Arithmetic Expressions using TSQL By leszek_g
;with cte as -- create prn
(
select
x.id
,x.expr
,x.e
,1 n
,cast(case
when patindex('[0-9X]%',x.e) > 0 then ''
else x.e
end as varchar(max)) stack
,cast(case
when patindex('[0-9X]%',x.e) > 0 then x.e
else ''
end as varchar(max)) output
from
(
select
t.id
,replace(t.expr,'^','p') expr
,left(t.expr,1) e
from TC48 t
) x
union all
select
y.id
,y.expr
,y.e
,y.n
,case
when patindex('[+-]%',y.e) > 0
then case
when y.i1 = 0
then y.e + y.stack
else
coalesce(y.e + stuff(y.stack,1,y.j1 - 1,''),y.e)
end
when patindex('[*/]%',y.e) > 0
then case
when y.i2 = 0
then y.e + y.stack
else
coalesce(y.e + stuff(y.stack,1,y.j2 - 1,''),y.e)
end
when patindex('p%',y.e) > 0
then case
when y.i3 = 0
then y.e + y.stack
else
coalesce(y.e + stuff(y.stack,1,y.j3 - 1,''),y.e)
end
when y.e = '('
then '(' + y.stack
when y.e = ')'
then stuff(y.stack,1,patindex('%(%',y.stack),'')
else y.stack
end stack
,case
when patindex('[0-9X]%',y.e) > 0
then y.output + y.e
when patindex('[+-]%',y.e) > 0 and y.i1 > 0
then y.output + coalesce(left(y.stack,nullif(y.j1,0)-1),y.stack)
when patindex('[*/]%',y.e) > 0
then y.output + coalesce(left(y.stack,nullif(y.j2,0)-1),y.stack)
when patindex('p%',y.e) > 0
then y.output + coalesce(left(y.stack,nullif(y.j3,0)-1),y.stack)
when y.e = ')'
then y.output + left(y.stack,patindex('%(%',y.stack)-1)
else y.output
end output
from
(
select
c.id
,c.expr
,substring(c.expr,c.n + 1,1) e
,c.n + 1 n
,c.stack
,c.output
,patindex('[p*/+-]%',c.stack) i1
,patindex('[p*/]%',c.stack) i2
,patindex('p%',c.stack) i3
,patindex('%(%',c.stack) j1
,patindex('%[(+-]%',c.stack) j2
,patindex('%[(*/+-]%',c.stack) j3
from cte c
where c.n < len(c.expr)
) y
)
,cte2 as
(
select
x.id
,x.output + x.stack rpn
from
(
select
c.id
,c.stack
,c.output
,row_number() over(partition by c.id order by c.n desc) rn
from cte c
) x
where x.rn = 1
)
,cte3 as -- first pass (to first X)
(
select
c.id
,c.rpn
,1 n
,cast(case
when left(c.rpn,1) = 'X' then ''
else cast(left(c.rpn,1) as char(23))
end
as varchar(8000)) stack
from cte2 c
union all
select
x.id
,x.rpn
,x.n + 1
,case
when x.v = '+' then convert(char(23),x.f1 + x.f2,2) + x.rest
when x.v = '-' then convert(char(23),x.f1 - x.f2,2) + x.rest
when x.v = '*' then convert(char(23),x.f1 * x.f2,2) + x.rest
when x.v = '/' then convert(char(23),x.f1 / x.f2,2) + x.rest
when x.v = 'p' then convert(char(23),power(x.f1,x.f2),2) + x.rest
else cast(x.v as char(23)) + x.stack
end
from
(
select
c.id
,c.rpn
,c.n
,c.stack
,substring(c.rpn,c.n + 1,1) v
,cast(substring(c.stack,24,23) as float(53)) f1
,cast(left(c.stack,23) as float(53)) f2
,stuff(c.stack,1,46,'') rest
from cte3 c
where c.n < len(c.rpn) and substring(c.rpn,c.n + 1,1) != 'X' and left(c.rpn,1) != 'X'
) x
)
,cte4 as
(
select
x.id
,x.rpn
,x.stack
from
(
select
c.id
,case
when patindex('X%',c.rpn) > 0 then c.rpn
else stuff(c.rpn,1,c.n,'')
end rpn
,c.stack
,row_number() over (partition by c.id order by c.n desc) rn
from cte3 c
) x
where x.rn = 1
)
,cte5 as -- second pass (join Tally)
(
select
c.id
,c.rpn
,t.x0 + t.dx * tl.N x
,1 n
,cast(case
when left(c.rpn,1) = 'X' then convert(char(23),t.x0 + t.dx * tl.N,2) + c.stack
else c.stack
end
as varchar(8000)) stack
from TC48 t
inner join cte4 c on t.id = c.id
inner join tsqlc_Tally tl on tl.N < t.points
union all
select
x.id
,x.rpn
,x.x
,x.n + 1
,case
when x.v = '+' then convert(char(23),x.f1 + x.f2,2) + x.rest
when x.v = '-' then convert(char(23),x.f1 - x.f2,2) + x.rest
when x.v = '*' then convert(char(23),x.f1 * x.f2,2) + x.rest
when x.v = '/' then convert(char(23),x.f1 / x.f2,2) + x.rest
when x.v = 'p' then convert(char(23),power(x.f1,x.f2),2) + x.rest
when x.v ='X' then convert(char(23),x.x,2) + x.stack
else cast(x.v as char(23)) + x.stack
end
from
(
select
c.id
,c.rpn
,c.x
,c.n
,c.stack
,substring(c.rpn,c.n + 1,1) v
,cast(substring(c.stack,24,23) as float(53)) f1
,cast(left(c.stack,23) as float(53)) f2
,stuff(c.stack,1,46,'') rest
from cte5 c
where c.n < len(c.rpn)
) x
)
select
t.expr
,z.x
,cast(z.stack as float(53)) value
from TC48 t
inner join
(
select
c.id
,c.x
,c.stack
,row_number() over(partition by c.id,c.x order by c.n desc) rn
from cte5 c
) z on t.id = z.id and z.rn = 1
order by t.expr,z.x
option(maxrecursion 0,force order)
Sr# StartTime Reads Writes CPU Duration
--- ------------------- ----------- ----------- ----------- --------
1 Mar 26 2011 2:22PM 4418492 140 5797 6.262
2 Mar 26 2011 2:23PM 4418493 139 5843 6.294
3 Mar 26 2011 2:24PM 4418531 143 5907 6.240
4 Mar 26 2011 2:26PM 4418551 147 5875 6.243
5 Mar 26 2011 2:27PM 4418549 151 5875 6.230