\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
Primeira Lista de Exerc\'\i cios -- Entrega: 17 de mar\c co
\end{center}

\begin{enumerate}
\item 
Considere 6 carros de trem numerados de 1 a 6 na entrada do estacionamento
em forma de pilha. \'E poss\'\i vel trocar a ordem dos vag\~oes para 
154632? E para 154623?

\item 
As opera\c c\~oes de colocar e tirar os $n$ vag\~oes do estacionamento podem
ser codificadas concisamente usando a letra E para ``empilhar'' (ou colocar 
um vag\~ao no estacionamento) e D para ``desempilhar'' (ou tirar um 
vag\~ao). Chamamos uma seq\"u\^encia de E's e D's de {\em admiss\'\i vel}
se cont\'em $n$ E's, $n$ D's e as opera\c c\~oes codificadas podem ser 
realizadas. Por exemplo, a seq\"u\^encia EDEEEEDDEEEDDDDD \'e admiss\'\i vel, 
enquanto a seq\"u\^encia EDDEEEDD n\~ao \'e admiss\'\i vel. Formule uma 
regra que permita diferenciar as seq\"u\^encias admiss\'\i veis das que n\~ao 
s\~ao. 

\item 
Mostre que \'e poss\'\i vel obter uma permuta\c c\~ao $p_1, p_2,\dots,p_n$
a partir de $1,2,\dots,n$ usando uma pilha se e somente se n\~ao 
existirem \'\i ndices $i,j$ e $k$
tais que $i < j < k$ e $p_k < p_i < p_j$. 

\item 
Considere agora um estacionamento de trens na forma de uma fila dupla, e 
$n$ trens numerados seq\"uencialmente na entrada. \'E poss\'\i vel obter 
todas as permuta\c c\~oes na sa\'\i da? 

\item 
a. Fa\c ca um programa que leia uma seq\"u\^encia de $n$ (,[,\{,\},] e ) 
e, utilizando uma pilha, decide se a seq\"u\^encia \'e bem formada. \\
b. Qual o maior tamanho (em fun\c c\~ao de $n$) que a pilha pode assumir? 
D\^e um exemplo de entrada em que isso ocorre. 

\item
Passe a express\~ao aritm\'etica abaixo para a nota\c c\~ao posfixa,
indicando para cada caractere lido o conte\'udo da pilha de operadores. 
\[ A + B * (C + D) /E - B - D \]
\end{enumerate}
\end{document}