1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{../style}

     4 \usepackage{../langs}

     5 \usepackage{disclaimer}

     6 \usepackage{tikz}

     7 \usepackage{pgf}

     8 \usepackage{pgfplots}

     9 \usepackage{stackengine}

    10 %% \usepackage{accents}

    11 \newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}

    12 \usepackage{ulem}

    13 

    14 \begin{document}

    15 

    16 % BF IDE

    17 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5

    18   

    19 \section*{Core Part 3 (Scala, 3 Marks)}

    20 

    21 \mbox{}\hfill\textit{``[Google’s MapReduce] abstraction is inspired by the}\\

    22 \mbox{}\hfill\textit{map and reduce primitives present in Lisp and many}\\

    23 \mbox{}\hfill\textit{other functional languages.''}\smallskip\\

    24 \mbox{}\hfill\textit{ --- Dean and Ghemawat, who designed this concept at Google}

    25 \bigskip

    26 

    27 \IMPORTANT{This part is about the shunting yard algorithm by Dijkstra.

    28   The preliminary part is due on \sout{\cwEIGHT{}} \textcolor{red}{11 December}

    29   at 5pm and worth 3\%.

    30   Any 1\% you achieve in the preliminary part counts as your

    31   ``weekly engagement''.}

    32 

    33 \noindent

    34 Also note that the running time of each part will be restricted to a

    35 maximum of 30 seconds on my laptop.  

    36 

    37 \DISCLAIMER{}

    38 

    39 \subsection*{Reference Implementation}

    40 

    41 This Scala assignment comes with two reference implementations in

    42 form of \texttt{jar}-files. This allows

    43 you to run any test cases on your own computer. For example you can

    44 call Scala on the command line with the option \texttt{-cp

    45   postfix.jar} and then query any function from the

    46 \texttt{postfix.scala} file (similarly for file \texttt{postfix2.scala}). As

    47 usual you have to prefix the calls with \texttt{C3a} and

    48 \texttt{C3b}, respectively.

    49 

    50 

    51 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

    52 $ scala -cp postfix.jar

    53 

    54 scala> C3a.syard(C3a.split("( 5 + 7 ) * 2"))

    55 val res0: C3a.Toks = List(5, 7, +, 2, *)

    56 \end{lstlisting}%$

    57 

    58 

    59 \subsection*{Hints}

    60 

    61 \noindent

    62 \textbf{For Core Part 3:} useful operations for determining

    63 whether a string is a number are \texttt{.forall} and \texttt{.isDigit}.

    64 One way to calculate the the power operation is to use \texttt{.pow}

    65 on \texttt{BigInt}s, like \texttt{BigInt(n).pow(m).toInt}.

    66 \bigskip

    67 

    68 

    69 \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)}

    70 

    71 The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,

    72 an influential computer scientist who developed many well-known

    73 algorithms. This algorithm transforms the usual infix notation of

    74 arithmetic expressions into the postfix notation, sometimes also

    75 called reverse Polish notation.

    76 

    77 Why on Earth do people use the postfix notation? It is much more

    78 convenient to work with the usual infix notation for arithmetic

    79 expressions. Most modern pocket calculators (as opposed to the ones used 20

    80 years ago) understand infix notation. So why on Earth? \ldots{}Well,

    81 many computers under the hood, even nowadays, use postfix notation

    82 extensively. For example if you give to the Java compiler the

    83 expression $1 + ((2 * 3) + (4 - 3))$, it will generate the Java Byte

    84 code

    85 

    86 \begin{lstlisting}[language=JVMIS,numbers=none]

    87 ldc 1 

    88 ldc 2 

    89 ldc 3 

    90 imul 

    91 ldc 4 

    92 ldc 3 

    93 isub 

    94 iadd 

    95 iadd

    96 \end{lstlisting}

    97 

    98 \noindent

    99 where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},

   100 \texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this

   101 is the arithmetic expression in postfix notation.\bigskip

   102 

   103 \noindent

   104 The shunting yard algorithm processes an input token list using an

   105 operator stack and an output list. The input consists of numbers,

   106 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of

   107 the assignment we assume the input is always a well-formed expression

   108 in infix notation.  The calculation in the shunting yard algorithm uses

   109 information about the

   110 precedences of the operators (given in the template file). The

   111 algorithm processes the input token list as follows:

   112 

   113 \begin{itemize}

   114 \item If there is a number as input token, then this token is

   115   transferred directly to the output list. Then the rest of the input is

   116   processed.

   117 \item If there is an operator as input token, then you need to check

   118   what is on top of the operator stack. If there are operators with

   119   a higher or equal precedence, these operators are first popped off

   120   from the stack and moved to the output list. Then the operator from the input

   121   is pushed onto the stack and the rest of the input is processed.

   122 \item If the input is a left-parenthesis, you push it on to the stack

   123   and continue processing the input.

   124 \item If the input is a right-parenthesis, then you pop off all operators

   125   from the stack to the output list until you reach the left-parenthesis.

   126   Then you discharge the $($ and $)$ from the input and stack, and continue

   127   processing the input list.

   128 \item If the input is empty, then you move all remaining operators

   129   from the stack to the output list.  

   130 \end{itemize}  

   131 

   132 \subsubsection*{Tasks (file postfix.scala)}

   133 

   134 \begin{itemize}

   135 \item[(1)] Implement the shunting yard algorithm described above. The

   136   function, called \texttt{syard}, takes a list of tokens as first

   137   argument. The second and third arguments are the stack and output

   138   list represented as Scala lists. The most convenient way to

   139   implement this algorithm is to analyse what the input list, stack

   140   and output list look like in each step using pattern-matching. The

   141   algorithm transforms for example the input

   142 

   143   \[

   144   \texttt{List(3, +, 4, *, (, 2, -, 1, ))}

   145   \]

   146 

   147   into the postfix output

   148 

   149   \[

   150   \texttt{List(3, 4, 2, 1, -, *, +)}

   151   \]  

   152   

   153   You can assume the input list is always a  list representing

   154   a well-formed infix arithmetic expression.\hfill[1 Mark]

   155 

   156 \item[(2)] Implement a compute function that takes a postfix expression

   157   as argument and evaluates it generating an integer as result. It uses a

   158   stack to evaluate the postfix expression. The operators $+$, $-$, $*$

   159   are as usual; $/$ is division on integers, for example $7 / 3 = 2$.

   160   \hfill[1 Mark]

   161 \end{itemize}

   162 

   163 \subsubsection*{Task (file postfix2.scala)}

   164 

   165 \begin{itemize}

   166 \item[(3/4)] Extend the code in (1) and (2) to include the power

   167   operator.  This requires proper account of associativity of

   168   the operators. The power operator is right-associative, whereas the

   169   other operators are left-associative.  Left-associative operators

   170   are popped off if the precedence is bigger or equal, while

   171   right-associative operators are only popped off if the precedence is

   172   bigger.\hfill[1 Marks]

   173 \end{itemize}

   174 

   175 \end{document}

   176 

   177 

   178 %%% Local Variables: 

   179 %%% mode: latex

   180 %%% TeX-master: t

   181 %%% End: