Push Pop

This is an algorithm trace task. No implementation is required.

The following algorithm uses one procedure and five functions.

The procedure PUSH(anArray, top, ch) first adds one to the value of top and then stores the single character held in ch in the one-dimensional array anArray at anArray[top].

The function POP(anArray, top) returns the character held in anArray[top] and then takes 1 off the value of top.

The function NEXTCHAR(str) returns the next character in its argument str which is a string.

The functions F(ch), G(ch) and R(ch) take a single character as input and return a value according to the table below:

For example

F(a single letter) = 7, G(a single letter) = 8 and R(a single letter) = 1

That is

F(”a”) = 7, G(”b”) = 8 and R(”c”) = 1

In the algorithm, & joins two strings together (concatenation). 

For example,”a + b” &”)” = ”a + b )”

The table below shows the values of current, anArray, newString and rank and the output when the input string is “a+b”

Produce a similar table for each of the following input strings.

  1. ”cd” [6]
  2. ”p*(q” [9]
  3. ”(v-w)*(x+y)” [17]

In your table, you should work from left to right and at the end of a row you should move onto the next row. You do not need to write a value again if it is the same as in the previous row.

This task was worth 32 Marks.  It was an algorithm trace task. No implementation is required that originally appeared in OCR 2507 Task 2 Jun 2008.  All rights and copyright to OCR.  Please refer to the OCR Copyright Statement for further information.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.