Questão 171217

• Banca: FGV
• Órgão: MEC
• Ano: 2009
• Provas: FGV - 2009 - MEC - Administrador de Banco de Dados; FGV - 2009 - MEC - Analista de Sistemas; FGV - 2009 - MEC - Analista de Teste de Qualidade; FGV - 2009 - MEC - Arquiteto de Sistemas; FGV - 2009 - MEC - Desenvolvedor
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

No contexto das estruturas de dados avançadas como listas, pilhas, filas e árvores é comum se encontrar referência à notação polonesa reversa. Nesse sentido, a expressão X*(Y+W)/(X-Y) é representada nessa notação, como:

• A. XYW+*XY/-
• B. XYW+*XY-/
• C. XYW+*/XY-
• D. XYW*+XY-/
• E. XYW*+XY/-

Gabarito: B

Comentários

•  

  • Notação Polonesa Reversa (ou posfix): é como a polonesa na qual os operandos aparecem após os operandos.
  
  Exemplo: 
  tradicional: A * B - C / D 
  polonesa reversa: A B * C D / -

• só corrigindo... a NPR ou Notação Polonesa Reversa é a notação a qual os OPERADORES aparecem após os OPERANDOS, esta é a mesma notação que se usam normalmente nas calculadoras cientificas como a HP 12C.

•  X*(Y+W)/(X-Y)
  
  na notação polonesa inversa primeiro temos que colocar os operandos e em seguida os operadores. (posfixada)
  Então:
  
  1. temos o primeiro operando: X
  2. o segundo: Y+W = YW+
  3. posfixando o operador multiplicação: XYW+*  (este tb é o primeiro operando da divisão)
  4. segundo operando da divisão:  X-Y = XY-
  5. juntando os operandos e posfixando o operador divisão: XYW+* XY-/ 
  
  Para notarmos a diferença vamos fazer a Notação Polonesa Normal, está é prefixada (operadores primeiro e operandos depois). E vem da operação mais "interna" para a mais "externa" (por isso a inversa é considerada mais rápida).
  
  1. operador mais interno é a divisão: /
  2. Primeiro operando da divisão: X*(Y+W) = *X+YW
  2.1. operador mais interno é a multiplicação (respeite os parênteses) = *
  2.2. primeiro operando da * = X
  2.3. segundo operando da * = Y+W = +YW
  3. Segundo operando da divisão = X-Y = -XY
  4. Concatenando os passos =  /*X+YW-XY
  
  Repare que a ordem das variáveis é a mesma nas três notações.
  
  
  
  
  
• Para este tipo de questão, eu aconselho fazer a arvore binaria, dai fica facil a resolução sem medo, vejamos (desculpe o desenho, mas é o que da pra fazer com mao livre, rs). A partir do enunciado, construimos a arvore abaixo e dela podemos derivar as outras ordens:
  
  Ordem Prefixa (Polonesa): /*X+YW-XY
  Ordem Infixa (dada no enunciado): X*(Y+W)/(X-Y)
  Ordem Pos-fixa (Polonesa reversa): XYW+*XY-/
  
  Bons estudos!!!
• Na notação polonesa invertida os operadores aparecem na ordem em que serão realmentes executados durante a avaliação da expressão.