• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 280
  • Last Modified:

Help on Question


I have the following question to answer but my text books are not breaking it down enough for me to understand, could anyone please let me know in more simple terms how to work it all out. I will supply the whole question so that you know what is being asked.
a specification of a function LASTAT is given below. In this, we number positions in the stack s from the top, so that the top item is at position 1, the item below this is at position 2, and so on. So for example, if s is the stack [5,4,3,4,33,22,11] then the item 11 is at position 1, the item 22 is at position 2 and so on.

In the specification below, the term 'last' is used  to refer to the occurence of num in s whose position os largest when numbered in this was

function LASTAT (s in Stack of Int, num in Int) return in Int
pre  true
post The returned value gives the position of the last occurence of num in s. If s is empty, or contains no copies of num, then the returned value is 0.

the questions are as follows

code in XImp is intended to implement LASTAT

function LASTAT(s,num)
{  /* XImp*/
var pos in Int
Var ret in Int
Var temp in Stack of Int
temp <-- s
for (pos <-- 0 to 4)
if (PEEK(temp) == num) then
{ ret <-- pos}
temp <-- POP(temp)
return ret

Q1.  If the stack s is [3,1,3,4,5] and num is 3, give a trace table giving the values of the variables pos, int, temp before and after the loop is entered, and after each execution of thebody of the loop

Q2. The trace in Q1 should show that XImp is not a correct implementation of LASTAT. Explain why the trace shows the implementation to be incorrect.

Q3.  Explain how XIMP might be modified to make it correct. show the changes that need to be made
As i said before I need some idiot notes as to how to answer this question, and i am not asking anyone to give me the answers unless they want to, but any help or information you can give will be grately recieved as I am desperate to understand this.

  • 2
2 Solutions
Won't give you the answer indeed ... however, here is a pointer : LASTAT might not be working according to specification

You say : s is the stack [5,4,3,4,33,22,11] then the item 11 is at position 1 (remember... position ONE)
What happens when you run LASTAT(s, 11) ?
Since there is only one number 11 in the stack, it should return 1, not ? (like you said before)

When you run it through the code and build a trace table, you will see that LASTAT(s, 11) != 1 (although we were clearly expecting 1)

Point it, take a look at the how the stack is indexed (from the specification and the how the code behaves).
Probably you will see a mismatch (unless you gave us some incorrect information)

-- Geert

One thing that might help is to redraw your stack, and add the position, or index associated with each value.
For example, instead of using a horizontal representation, change it to vertical:

 7 :  5
 6 :  4
 5 :  3
 4 :  4
 3 : 33
 2 : 22
 1 : 11

  The way stacks were explained to me (a long time ago, in a galaxy far far away), was that they act like a plate dispenser at the cafeteria.  A bunch of clean plates are "pushed" onto the stack, and then are available to be "popped", one at a time, for each customer.

  Using this illustration, your stack (above), contains seven items (values).

  As suggested by Geert, take the code, and "play computer".  For each variable that is declared, draw a box to hold it value, and write the variable name by the box.  For each statement in your routine, make the appropriate changes to your variable values, and see how these values change as the instructions are executed.
big hint:  what is that significance of the HARD-CODED number 4 in this line of the prposed implementation:

for (pos <-- 0 to 4)

Thanks for the 'A', hopefully things are working out well for you. Good luck
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now