**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 Algorithm**

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.

- ”cd” [6]
- ”p*(q” [9]
- ”(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.*