In ACSL Contest 2, you would face the questions covering the following three topics.
|Question Type||Number of Questions|
These topics would be covered in the following pages.
Next page: 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
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
|LCIRC-n||Basically means ‘Left CIRCular’|
Shift the entire string to the left and move the rest to the right
|RSHIFT-n||Shift the entire string to the right and put 0 for empty spaces||RSHIFT-3 10001|
|RSHIFT-n||Shift the entire string to the left and put 0 for empty spaces||LSHIFT-3 10001|
|AND||and operation for every bit|
|OR||or operation for every bit|
|NOT||not operation for every bit|
|XOR||xor operation for every bit|
For this part, you would have to remember the following function:
|MULT(n1,n2)||$n1 * n2$|
|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