Results 1 to 6 of 6

012206, 14:27 #1Registered User
 Join Date
 Jan 2006
 Posts
 4
Implementing A Stack In SQL Server
Hi,
I need to implement a stack using Sql Server.
The basic table is simple:
id (int), val (char(10)).
Basically I want a recursive EvaluateStack stored procedure. This should select the topmost value from the stack, and then either return it or (in the case of an operator) recursively call itself in order to get a left hand and a righthand operator. So:
(pseudocode)
SELECT val FROM STACK WHERE id=@Count
CASE WHEN val="+"
lhs=EXEC EvaluateStack
rhs=EXEC EvaluateStack
return lhs+rhs
SELECT @Count=@Count1
Etc. etc.
The problem is, being a bit rusty with Sql Server, can anyone give me some pointers how to best implement the conditional logic?
I.e. I want to evaluate the value in the row at the bottom of the table, then if it is an operator EXECUTE this stored procedure again.
Thanks in advance. Another peculiarity is that '+' evaluates to true using Sql Server's ISNUMERIC function.

012306, 15:53 #2Purveyor of Discontent
 Join Date
 Mar 2003
 Location
 The Bottom of The Barrel
 Posts
 6,102
Seems like a cursor would work here...

012306, 18:03 #3Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
There are two ways to implement an arithmetic stack. One way is "Combined", where both operators and operands exist on a single stack. The other way is "Discrete", where there is one stack for operators and a separate stack for operands. Based on your description of the stack manipulation, you're implementing a combined stack. A combined stack can only be evaluated iteratively (there can't be a set based solution), so you need to implement a cursor to validate/evaluate the contents of the stack.
PatP

012606, 08:36 #4Registered User
 Join Date
 Jan 2006
 Posts
 4
Thanks for your replies. I have a basic stack table with Position int and Val char columns. (There will be more columns later but right now I am just trying to get the basic mechanics working).
I am trying to write a stored procedure to evaluate this stack. This proc has a position parameter and result out parameter. Basically it should iterate through each row and either return the number if that is what it finds on the stack, or, if it finds an operator recursively call itself to get two operands and manipulate them according to what the operator is and return that result. I do not want to use a cursor. In fact a friend of mine has got a version working in Sybase, which I'll print at the end. For now I have a flawed Sql Server version, which I'd be grateful for comments on. Basically I'm not sure how to make it recursively call itself, and still go through all the necessary rows.
FLAWED SQL SERVER IMPLEMENTATION OF SP_STACKEVAL:
CREATE PROCEDURE dbo.EvalStack
@InPos INT=NULL,
@Result INT=NULL OUT
AS
DECLARE @VAL CHAR(10)
IF @InPos IS NULL
BEGIN
SELECT @InPos=COUNT(*) FROM STACK
WHERE StackSubSetId=@StackSubSetId, TODO!
END
IF @InPos>0
BEGIN
SELECT @VAL=Val FROM STACK
WHERE Position=@InPos
SELECT @InPos=@Inpos1
IF @VAL LIKE '%+%'
BEGIN
DECLARE @lhs int, @rhs int, @tmp_rslt int
EXEC EvalStack @InPos, @Result=@tmp_rslt OUT
SELECT @lhs=@tmp_rsltEND
EXEC EvalStack @InPos, @Result=@tmp_rslt OUT
SELECT @rhs=@tmp_rsltEND
ELSE
RETURN @VAL
CORRECT SYBASE IMPLEMENTATION:
 Stack  pos counts up from 0 (bottom of stack).
create table #stack (
pos int not null primary key,
value varchar(255) not null
)
go
create procedure eval_stack @pos int in, @new_pos int output, @result
int output as begin
 Pop one item off the stack.
declare @top varchar(255)
select @top = value from #stack where pos = @pos
select @pos = @pos  1
 See if it's the + operator.
if @top = '+' begin
declare @lhs int, @rhs int, @tmp_pos int
exec eval_stack @pos = @pos, @new_pos = @tmp_pos output,
@result = @lhs output
select @pos = @tmp_pos
exec eval_stack @pos = @pos, @new_pos = @tmp_pos output,
@result = @rhs output
select @pos = @tmp_pos
select @new_pos = @pos
select @result = @lhs + @rhs
return 0
end
 Insert code for other operators here.
 Not an operator, must be a number.
select @new_pos = @pos
select @result = convert(int, @top)
return 0
end
go
 To test it:
declare @new_pos int, @result int, @string varchar(255)
exec eval_stack @pos = 2, @new_pos = @new_pos output, @result = @result
output
select @string = convert(varchar(255), @result)
print @string
go

012606, 08:54 #5Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
Has the teacher posted this assignement somewhere that we could look at it? If not, could you scan the assignment handout so we could look at that? Just based on the way that the problem is stated, I'm concerned that they've hidden some "interesting" details in the assignment that would cause us to give you an incorrect solution if we just solved it in a straightforward way. You'll often see that when there's a "hidden agenda" which is obvious from the details of how something is presented like this.
PatP

012606, 09:08 #6Registered User
 Join Date
 Jan 2006
 Posts
 4
Sure, the requirement is basically as follows.
This is to store some mathematical expressions in a database table, imitating a classic FIFO stack. Expressions could range in complexity from (2+2) to ((reference_to_a_value_in_anothe_table, stored in 'dbo.tablename.columnname/rowid' form)+100/2) and so on and on. So the basic idea is a stack (which will later include a column to differentiate between expressions), and a stored procedure to evaluate each expression. It needs to be done on a db because network latency in this case must be avoided. I think I'm most of the way there, I'm just getting thrown by the SQL SERVER TSQL code to go through all the rows and either return a numerical value OR recursively call itself until it finds a numerical value and include that in an expression. I.e. the basic logic is:
PROC EvalStack
@InPos Int
@Result Char (10)
 GO THROUGH ALL THE ROWS IN THE STACK
IF THE VAL FOUND ON THE STACK IS A NUMBER, COOL, RETURN THAT
IF THE VAL FOUND ON THE STACK IS AN OPERATOR,
DECLARE TWO TEMP VARIABLES FOR LEFTHAND OPERAND AND RIGHTHAND OPERAND, POP THE STACK TO GET THEM, AND THEN DO WHATEVER THE OPERATOR IS FOR, THEN RETURN THE RESULTANT VALUE