\documentclass[11pt]{article}
\usepackage{times}
\usepackage{pifont} % for fancy bullets
\topmargin  -0.3truein
\headheight 0.3truein
\headsep    0.3truein
\footskip 0.6in
\newcommand{\headerfont}{\fontfamily{phv}\fontseries{b}\fontshape{n}%
\fontsize{10}{12pt}\selectfont}
\newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}%
\fontsize{11}{13pt}\selectfont}
\newcommand{\largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}%
\fontsize{13}{15pt}\selectfont}
\newcommand{\largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}%
\fontsize{13}{15pt}\selectfont}
\newcommand{\Largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}%
\fontsize{19}{21pt}\selectfont}
\newcommand{\Largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}%
\fontsize{19}{21pt}\selectfont}

%
%%%%%%%%%%%%%%%%%%%   My Headings %%%%%%%%%%%%%%%%%%%%%
%
\makeatletter % Make '@' a letter to allow access to private macros
%
\def\ps@myheadings{
  \def\@oddhead{\framebox[\mywidth]{\headerfont \rule[3.1mm]{0mm}{0mm}
     \hspace{0.7mm}\lefthead, \today \hfill 
     Page~~\thepage~~of~~\pageref{'thatsall'}~~}}
  \def\@oddfoot{}
  \def\@evenhead{}
  \def\@evenfoot{}
}
\makeatother % Remove '@' a non-letter to disallow access to pvt macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% next line must come after the headings stuff!
\pagestyle{myheadings}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mywidth}{6.0in}
\newcommand{\lefthead}{CS1723: Data Structures, Assignment 5}
\newcommand{\st}{\rule[-.8mm]{0mm}{2mm}}
\newcommand{\longst}{\rule[-3mm]{0mm}{2mm}}
\newcommand{\outerbaselinesep}{14pt}
\topmargin -0.5in
\oddsidemargin 0.25in
\evensidemargin 0.25in
\textwidth \mywidth
\textheight 9.2in
\parindent 0mm %10mm
\parskip 3mm

\fboxrule=0.3mm

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% make everything sloppy
\sloppy

\begin{center}
%{\largebold The University of Texas at San Antonio \\
%Computer Science Division \\
%San Antonio, Texas  78249} \\

%\vspace{0.4in}

{\largebold
  CS 1723,  Data Structures,
    Fall Semester, 1998\longst  \\
    Programming Assignment 5, Due October 9, 1998\longst } \\
 {\largeboldital  Translation to Reverse Polish}
\end{center}

\baselineskip=\outerbaselinesep

\vspace{-0.2in}
{\bf The Assignment:}
For this assignment you will write a program
{\tt translate} that will translate an ordinary
arithmetic expression into {\em reverse Polish} form.
This program should be used in conjunction with the program {\tt evaluate}
of the earlier Assignment 2 to find the final value of an
input arithmetic expression.
For the final runs after initial testing,
you can pipe the output of {\tt translate} in
as input to {\tt evaluate}, so that you use the command:

\hspace*{17mm}{\tt runner\% {\ttb translate  <sourcefile | evaluate}}

%%%\vspace{-0.2in}
The input source will be made up of the following elements:

\vspace{-0.2in}
\begin{list}{dummy}{\parsep=1mm \itemsep=1mm}
\item [\ding{97}] single-digit integer constants, 
   {\tt 0}, {\tt 1}, {\tt 2}, {\tt 3}, {\tt 4}, {\tt 5}, 
   {\tt 6}, {\tt 7}, {\tt 8}, or {\tt 9}.
\item [\ding{97}] operators: $\wedge$, {\tt *} {\tt /}, {\tt +}, or {\tt -}.
\item [\ding{97}] parentheses: {\tt (} and {\tt )}.
\item [\ding{97}] the special symbols: {\tt \#}  to terminate the whole input.
\end{list}

\vspace{-0.2in}
This assignment limits to single-digit integer constants
in order to keep things simpler.

For example, here is sample input source, which calculates one
root of the equation $y = x^2 + 3x + 2$:

\vspace{-0.2in}
\begin{verbatim}	
        ((3^2 - 4*1*2)^(1/2) - 3)/(2*1)#
\end{verbatim}

\vspace{-0.2in}
Notice that all {\em whitespace} (= space, newline, tab, etc.) should
be ignored on input.

{\bf Overall organization:} All files and programs should be contained in
a single directory: {\tt assign5}.  You will be
combining a new program (in three files) with the old
program from Assignment 2.

{\bf The program {\ttb translate.c}:}
Organize the program as (at least) {\em three} files:
{\tt translate.c}, {\tt tstack.h}, and {\tt tstack.c}.

The {\tt tstack.h} and {\tt tstack.c} files should implement a
stack of characters.
(You will probably want to add a function {\tt top()} that will
return the topmost character without popping it.)

In addition to {\tt main()}, the {\tt translate.c} file should
contain functions with prototypes

\vspace{-0.2in}
\begin{verbatim}
        void checkprec (char c, int *prec, char *assoc);
        int getnext(void);
\end{verbatim}

\vspace{-0.3in}
\begin{itemize}

\item The function {\tt checkprec()} should return the precedence
and associativity of the operator stored in the variable ``c'',
according to the following table:

\hspace{0.5in}
\begin{tabular}{|c|c|c|}
\hline
Operator  &  Precedence  &  Associativity \\ \hline\hline
$\wedge$  &      5       &       R        \\ \hline
   *      &      4       &       L        \\ \hline
   /      &      4       &       L        \\ \hline
   +      &      3       &       L        \\ \hline
   $-$    &      3       &       L        \\ \hline
   (      &      1       &       R        \\ \hline
   )      &      1       &       R        \\ \hline
\end{tabular}

There {\em must} be a static array of structures inside {\tt checkprec()}
which stores this information.  This structure {\em must} be initialized
using a list of initializers enclosed in braces, as shown
in Section 6.3 of the white book (page 133).

\item The function {\tt getnext()} should return the next
non-whitespace character.  (Use {\tt isspace()} in {\tt <ctype.h>}.)

\end{itemize}

\vspace{-0.1in}
The translation algoritm will be discussed in class. Notice that
for each non-whitespace character, the program must decide
whether to output it or to stack it.  Operands (digits and
letters) are always output immediately. Operators (including
parentheses) are always stacked, but in some cases not before
one or more other operators are popped and output.
The following rules apply:

\vspace{-0.1in}
\begin{enumerate}
\item Always push a left parenthesis.
\item Always push an operator if the stack is empty, if an
  operator of lower precedence is on top, or if an operator of equal
  precedence is on top and right-to-left associativity applies.
\item Otherwise pop and output the stacktop, and try rules
  1 and 2 again.
\item A left and a right parenthsis (right above left) on the stack
are always simply deleted.
\item A \# character terminates the current input.  Ouput a \#
and terminate the program.
\end{enumerate}

\vspace{-0.1in}
The result of the sample input above should be:

\vspace{-0.2in}
\begin{verbatim}
        32^41*2*-12/^3-21*/#
\end{verbatim}

\vspace{-0.1in}
{\bf The initial {\ttb makefile} for {\ttb translate.c}:}
\vspace{-0.1in}
\begin{verbatim}
        # makefile for the translate program
        translate: translate.c tstack.c tstack.h
                cc -g -o translate translate.c tstack.c
        tlint:
                lint -m -u translate.c tstack.c
\end{verbatim}

\vspace{-0.1in}
{\bf The second program {\ttb evaluate.c}:}
Use the program that you wrote for Assignment 2.

\vspace{-0.1in}
{\bf Required Execution:}
You must try out the following table of input arithmetic
expressions, with the translations  and final values as shown.
(Some students may have trouble getting all of these to work
correctly; should should turn in your program anyway.)

\noindent
\begin{tabular}{|l|l|l|}
\hline
Input arithmetic expression  &  Output reverse Polish & Final value  \\ \hline\hline
\verb!2+3*4#!                         & \verb!234*+#!               & 14.000000 \\ \hline
\verb!3*4+5#!                         & \verb!34*5+#!               & 17.000000    \\ \hline
\verb!(2+3)*4#!                       & \verb!23+4*#!               & 20.000000  \\ \hline
\verb!(3*(2+4)/(5+1))-2#!             & \verb!324+*51+/2-#!         & 1.000000  \\ \hline
\verb!(5+3)^(2+1)^2#!                 & \verb!53+21+2^^#!           & 134217728.000000 \\ 
    \hline
\verb!2+3*4^5*6+7#!                   & \verb!2345^*6*+7+#!         & 18441.000000\\ \hline
\verb!((3^2-4*1*2)^(1/2)-3)/(2*1)#!   & \verb!32^41*2*-12/^3-21*/#! & -1.000000 \\ \hline
\verb!((2-3)^((4+1)*5)/6-(2-4)*7)-8#! & \verb!23-41+5*^6/24-7*-8-#! & 5.833333 \\ \hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{'thatsall'}
\end{document}