ACSL Contest 2

In ACSL Contest 2, you would face the questions covering the following three topics.

Question Type	Number of Questions
Pre/Post/Infix Notation	2
Bit-String Flicking	2
LISP Programming	1

These topics would be covered in the following pages.

Next page: Pre/Post/Infix Notation

[latexpage]

Pre/Post/Infix Notation

For this type of question, you would have to convert between different notations of expression or evaluate the expression provided. We would provide a brief introduction to the notations and then we will present the methods to covert them.

Introduction to different notations

When the computer processes an expression, it could be expressed in three ways, which are called just as the top heading suggested. These different notations are connected with binary trees. In most cases, we are using the infix notation, in which the binary operators are placed between the two numbers. A basic example would be the following expression:

However, there are two other ways of presenting the notations. The first one is called prefix notation, in which the binary operators are placed in front of the two numbers. An example would be the following:

The other type would be postfix notation, in which the binary operators are placed at the end of the two numbers. An example would be this:

They seemed to be irrelevant at first glance, but, after I tell you about the conversion in the following sections, you would found that the above three examples are actually the same thing.

Conversions between the different notations

When converting different notations, we often use the infix notation as a bridge during conversion. The following sections would show you how to present the different conversions.

Conversions between prefix and infix notations

When converting from prefix to infix notations, a good way would be trying to convert the sections which strictly follows the ‘operator-number1-number2‘ pattern. Let’s look at the following prefix expression example:

In order to convert this to infix notation, we could try to use the method I mentioned above. Notice that in most cases in ACSL, the $\uparrow$ represents the power function, where the first number is the base and the second is the exponential. So now let’s just get started. We would transverse the entire list of symbols until we reach finally an infix notation.

It might seem useful at first glance, but you would never be asked this type of question in the exam since its too easy. Instead, you would be asked to evaluate the prefix notation, which would be easier as you could use the result in every step instead. Let’s look at the following past paper question with its year indicated in the picture for Senior Contest.

To be honest, you could just follow the following steps to reach the results:

For the other way round, more questions occur as the infix notation could be quite complicated. Let’s look at the following example as a glance to how these type questions would be like:

At first glance, you might be scared by this question. But don’t panic. Just as the saying says, the best way to overcome the difficulty is to face it directly. Hence we could first try to remove the fraction lines and the square root symbols and convert them during the process. The following is the complete process during the expansion of the expression.

That’s all for converting between prefix and infix notations.

Converting between postfix and infix notations

When converting between postfix and infix notations, you would need basically the same skills as above, except always remember to look for number1-number2-operator when you are converting and put the operator at the back when you are converting to the postfix notations.

Converting between prefix and postfix notations

For this type of question, you could just use the infix notation as a bridge to convert.

Next Page: Bit-String Flicking

Bit-String Flicking

There is basically a table of commands that you shall remember as the commands:

Command	Explaination	Examples using 10001 and n=3
RCIRC-n	Basically means ‘Right CIRCular’ Shift the entire string to the right and move the rest to the left	RCIRC-3 10001 =00110
LCIRC-n	Basically means ‘Left CIRCular’ Shift the entire string to the left and move the rest to the right	LCIRC-3 10001 =01100
RSHIFT-n	Shift the entire string to the right and put 0 for empty spaces	RSHIFT-3 10001 =00100
RSHIFT-n	Shift the entire string to the left and put 0 for empty spaces	LSHIFT-3 10001 =00100
AND	and operation for every bit
OR	or operation for every bit
NOT	not operation for every bit
XOR	xor operation for every bit (same=0,different=1)

[latexpage]

LISP Programming

For this part, you would have to remember the following function:

Description	Explaination	Example
ADD(n1,n2)	$n1+n2$
SUB(n1,n2)	$n1-n2$
MULT(n1,n2)	$n1 * n2$
DIV(n1,n2)	$n1/ n2$
EXP(n1,n2)	$n1^{n2}$
SQUARE(n)	$n^{2}$
SET identifier list	assign the list value to the identifier	SET X (1 (23) 4)
CAR(list)	return the first element of the list	CAR X=1
CDR(list)	return the list without its fist element	CDR X=((23) 4)
REVERSE(list)	reverse the list	REVERSE X=(4 (23) 1)
CON(var1,var2)	connect two variables to form a list	CON(X,5)=(1 (23) 4 5)

I’m truely sorry for the uncomplete of this post for the lack of time. The rest two sections only contains the most essential information. I might update this post during the holiday later.

Daniel – author of this post