cws/core_cw03.tex
changeset 475 59e005dcf163
parent 471 135bf034ac30
equal deleted inserted replaced
474:b528d1d3d3c3 475:59e005dcf163
    62 \bigskip
    62 \bigskip
    63 
    63 
    64 
    64 
    65 \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)}
    65 \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)}
    66 
    66 
    67 The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
    67 The \textit{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
    68 an influential computer scientist who developed many well-known
    68 an influential computer scientist who developed many well-known
    69 algorithms. This algorithm transforms the usual infix notation of
    69 algorithms. This algorithm transforms the usual infix notation of
    70 arithmetic expressions into the postfix notation, sometimes also
    70 arithmetic expressions into the postfix notation, sometimes also
    71 called reverse Polish notation.
    71 called \textit{Reverse Polish Notation}.
    72 
    72 
    73 Why on Earth do people use the postfix notation? It is much more
    73 Why on Earth do people use the postfix notation? It is much more
    74 convenient to work with the usual infix notation for arithmetic
    74 convenient to work with the usual infix notation for arithmetic
    75 expressions. Most modern pocket calculators (as opposed to the ones used 20
    75 expressions. Most modern pocket calculators (as opposed to the ones used 20
    76 years ago) understand infix notation. So why on Earth? \ldots{}Well,
    76 years ago) understand infix notation. So why on Earth? \ldots{}Well,
    90 iadd 
    90 iadd 
    91 iadd
    91 iadd
    92 \end{lstlisting}
    92 \end{lstlisting}
    93 
    93 
    94 \noindent
    94 \noindent
    95 where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},
    95 where the command \texttt{ldc} loads a number onto the stack, and \texttt{imul},
    96 \texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
    96 \texttt{isub} and \texttt{iadd} perform arithmetic operations on the stack. Clearly, this
    97 is the arithmetic expression in postfix notation.\bigskip
    97 is the arithmetic expression from above but in postfix notation.\bigskip
    98 
    98 
    99 \noindent
    99 \noindent
   100 The shunting yard algorithm processes an input token list using an
   100 The shunting yard algorithm processes an input token list using an
   101 operator stack and an output list. The input consists of numbers,
   101 operator stack and an output list. The input consists of numbers,
   102 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
   102 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
   121   from the stack to the output list until you reach the left-parenthesis.
   121   from the stack to the output list until you reach the left-parenthesis.
   122   Then you discharge the $($ and $)$ from the input and stack, and continue
   122   Then you discharge the $($ and $)$ from the input and stack, and continue
   123   processing the input list.
   123   processing the input list.
   124 \item If the input is empty, then you move all remaining operators
   124 \item If the input is empty, then you move all remaining operators
   125   from the stack to the output list.  
   125   from the stack to the output list.  
   126 \end{itemize}  
   126 \end{itemize}
       
   127 
       
   128 \noindent
       
   129 BTW, the rules above are written ``If\ldots'', but this is because English does not
       
   130 include very sophisticated pattern matching. But clearly the rules above should be implemented
       
   131 in Scala using pattern matching.
       
   132 
   127 
   133 
   128 \subsubsection*{Tasks (file postfix.scala)}
   134 \subsubsection*{Tasks (file postfix.scala)}
   129 
   135 
   130 \begin{itemize}
   136 \begin{itemize}
   131 \item[(1)] Implement the shunting yard algorithm described above. The
   137 \item[(1)] Implement the shunting yard algorithm described above. The