% !TEX program = xelatex
\documentclass{article}
\usepackage{../styles/style}
\usepackage{../styles/langs}
\usepackage{disclaimer}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{pgfplots}
\usepackage{stackengine}
%% \usepackage{accents}
\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
\usepackage{ulem}

\begin{document}

% BF IDE
% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
  
\section*{Core Part 3 (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

\IMPORTANTNONE{}

\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-cli on the command line with the option \texttt{--extra-jars
  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{C3a} and
\texttt{C3b}, respectively.


\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
$ scala-cli --extra-jars postfix.jar

scala> C3a.syard(C3a.split("( 5 + 7 ) * 2"))
val res0: C3a.Toks = List(5, 7, +, 2, *)
\end{lstlisting}%$


\subsection*{Hints}

\noindent
\textbf{For Core Part 3:} useful operations for determining
whether a string is a number are \texttt{.forall} and \texttt{.isDigit}.
One way to calculate the the power operation is to use \texttt{.pow}
on \texttt{BigInt}s, like \texttt{BigInt(n).pow(m).toInt}.
\bigskip


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

The \textit{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 \textit{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 number onto the stack, and \texttt{imul},
\texttt{isub} and \texttt{iadd} perform arithmetic operations on the stack. Clearly, this
is the arithmetic expression from above but 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}

\noindent
BTW, the rules above are written ``If\ldots'', but this is because English does not
include very sophisticated pattern matching. But clearly the rules above should be implemented
in Scala using pattern matching.


\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: