diff -r 663c2a9108d1 -r 4de31fdc0d67 cws/pre_cw03.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/pre_cw03.tex	Mon Nov 02 02:31:44 2020 +0000
@@ -0,0 +1,168 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+\usepackage{disclaimer}
+\usepackage{tikz}
+\usepackage{pgf}
+\usepackage{pgfplots}
+\usepackage{stackengine}
+%% \usepackage{accents}
+\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
+
+
+\begin{document}
+
+% BF IDE
+% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
+  
+\section*{Preliminary Part 8 (Scala, 3 Marks)}
+
+\mbox{}\hfill\textit{``[Google’s MapReduce] abstraction is inspired by the}\\
+\mbox{}\hfill\textit{map and reduce primitives present in Lisp and many}\\
+\mbox{}\hfill\textit{other functional languages.''}\smallskip\\
+\mbox{}\hfill\textit{ --- Dean and Ghemawat, who designed this concept at Google}
+\bigskip
+
+\IMPORTANT{This part is about the shunting yard algorithm by Dijkstra.
+  The preliminary part is due on \cwEIGHT{} at 5pm and worth 3\%.}
+
+\noindent
+Also note that the running time of each part will be restricted to a
+maximum of 30 seconds on my laptop.  
+
+\DISCLAIMER{}
+
+\subsection*{Reference Implementation}
+
+This Scala assignment comes with two reference implementations in
+form of \texttt{jar}-files. This allows
+you to run any test cases on your own computer. For example you can
+call Scala on the command line with the option \texttt{-cp
+  postfix.jar} and then query any function from the
+\texttt{postfix.scala} file (similarly for file \texttt{postfix2.scala}). As
+usual you have to prefix the calls with \texttt{CW8a} and
+\texttt{CW8b}, respectively.
+
+
+\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
+$ scala -cp postfix.jar
+
+scala> CW8a.syard(CW8a.split("( 5 + 7 ) * 2"))
+val res0: CW8a.Toks = List(5, 7, +, 2, *)
+\end{lstlisting}%$
+
+
+\subsection*{Preliminary Part (3 Marks, files postfix.scala, postfix2.scala)}
+
+The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
+an influential computer scientist who developed many well-known
+algorithms. This algorithm transforms the usual infix notation of
+arithmetic expressions into the postfix notation, sometimes also
+called reverse Polish notation.
+
+Why on Earth do people use the postfix notation? It is much more
+convenient to work with the usual infix notation for arithmetic
+expressions. Most modern pocket calculators (as opposed to the ones used 20
+years ago) understand infix notation. So why on Earth? \ldots{}Well,
+many computers under the hood, even nowadays, use postfix notation
+extensively. For example if you give to the Java compiler the
+expression $1 + ((2 * 3) + (4 - 3))$, it will generate the Java Byte
+code
+
+\begin{lstlisting}[language=JVMIS,numbers=none]
+ldc 1 
+ldc 2 
+ldc 3 
+imul 
+ldc 4 
+ldc 3 
+isub 
+iadd 
+iadd
+\end{lstlisting}
+
+\noindent
+where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},
+\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
+is the arithmetic expression in postfix notation.\bigskip
+
+\noindent
+The shunting yard algorithm processes an input token list using an
+operator stack and an output list. The input consists of numbers,
+operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
+the assignment we assume the input is always a well-formed expression
+in infix notation.  The calculation in the shunting yard algorithm uses
+information about the
+precedences of the operators (given in the template file). The
+algorithm processes the input token list as follows:
+
+\begin{itemize}
+\item If there is a number as input token, then this token is
+  transferred directly to the output list. Then the rest of the input is
+  processed.
+\item If there is an operator as input token, then you need to check
+  what is on top of the operator stack. If there are operators with
+  a higher or equal precedence, these operators are first popped off
+  from the stack and moved to the output list. Then the operator from the input
+  is pushed onto the stack and the rest of the input is processed.
+\item If the input is a left-parenthesis, you push it on to the stack
+  and continue processing the input.
+\item If the input is a right-parenthesis, then you pop off all operators
+  from the stack to the output list until you reach the left-parenthesis.
+  Then you discharge the $($ and $)$ from the input and stack, and continue
+  processing the input list.
+\item If the input is empty, then you move all remaining operators
+  from the stack to the output list.  
+\end{itemize}  
+
+\subsubsection*{Tasks (file postfix.scala)}
+
+\begin{itemize}
+\item[(1)] Implement the shunting yard algorithm described above. The
+  function, called \texttt{syard}, takes a list of tokens as first
+  argument. The second and third arguments are the stack and output
+  list represented as Scala lists. The most convenient way to
+  implement this algorithm is to analyse what the input list, stack
+  and output list look like in each step using pattern-matching. The
+  algorithm transforms for example the input
+
+  \[
+  \texttt{List(3, +, 4, *, (, 2, -, 1, ))}
+  \]
+
+  into the postfix output
+
+  \[
+  \texttt{List(3, 4, 2, 1, -, *, +)}
+  \]  
+  
+  You can assume the input list is always a  list representing
+  a well-formed infix arithmetic expression.\hfill[1 Mark]
+
+\item[(2)] Implement a compute function that takes a postfix expression
+  as argument and evaluates it generating an integer as result. It uses a
+  stack to evaluate the postfix expression. The operators $+$, $-$, $*$
+  are as usual; $/$ is division on integers, for example $7 / 3 = 2$.
+  \hfill[1 Mark]
+\end{itemize}
+
+\subsubsection*{Task (file postfix2.scala)}
+
+\begin{itemize}
+\item[(3/4)] Extend the code in (1) and (2) to include the power
+  operator.  This requires proper account of associativity of
+  the operators. The power operator is right-associative, whereas the
+  other operators are left-associative.  Left-associative operators
+  are popped off if the precedence is bigger or equal, while
+  right-associative operators are only popped off if the precedence is
+  bigger.\hfill[1 Marks]
+\end{itemize}
+
+\end{document}
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: