Results 1 to 6 of 6
  1. #1
    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:

    (pseudo-code)
    SELECT val FROM STACK WHERE id=@Count
    CASE WHEN val="+"
    lhs=EXEC EvaluateStack
    rhs=EXEC EvaluateStack
    return lhs+rhs
    SELECT @Count=@Count-1
    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.

  2. #2
    Join Date
    Mar 2003
    Location
    The Bottom of The Barrel
    Posts
    6,102
    Seems like a cursor would work here...
    oh yeah... documentation... I have heard of that.

    *** What Do You Want In The MS Access Forum? ***

  3. #3
    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

  4. #4
    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=@Inpos-1

    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

  5. #5
    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

  6. #6
    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 T-SQL 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 LEFT-HAND OPERAND AND RIGHT-HAND OPERAND, POP THE STACK TO GET THEM, AND THEN DO WHATEVER THE OPERATOR IS FOR, THEN RETURN THE RESULTANT VALUE

Posting Permissions

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