Definição do Problema

O objetivo é avaliar uma expressão aritmética apresentada na forma de Notação Polonesa Inversa (RPN), fornecida como um array de strings. O resultado deve ser retornado como um número inteiro.

Regras importantes:

• Os operadores válidos são +, -, * e /.
• Os operandos podem ser inteiros ou outras expressões já avaliadas.
• A divisão entre dois inteiros deve ser truncada em direção a zero.
• A expressão é garantidamente válida e não conterá divisões por zero.

Exemplo de Entrada e Saída

Entrada: tokens = ["4", "13", "5", "/", "+"]
Saída: 6
Explicação: A expressão infixa equivalente é (4 + (13 / 5)), que resulta em 6 (considerando o truncamento da divisão).

Estratégia Algorítmica

A estrutura de dados ideal para resolver este problema é a Pilha (Stack). A lógica consiste em iterar sobre o array de tokens:

1. Se o token for um número, converta-o e empilhe-o.
2. Se o token for um operador, desempilhe os dois últimos valores. O primeiro valor desempilhado atua como operando direito, e o segundo como operando esquerdo.
3. Aplique a operação matemática correspondente e empilhe o resultado.

É crucial atentar-se à ordem dos operandos nas operações de subtração e divisão, pois estas não são comutativas e a ordem de desempilhamento inverte a posição original dos elementos.

Implementação em Java

Na implementação abaixo, utilizamos a interface Deque com ArrayDeque, que é a abordagem recomnedada no Java moderno em vez da classe legada Stack. Além disso, empregamos uma estrutura switch para otimizar a verificação dos operadores e melhorar a legibilidade.

import java.util.Deque;
import java.util.ArrayDeque;

public class RpnCalculator {
    public int evaluate(String[] tokens) {
        Deque<integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int rightOperand = stack.pop();
                    int leftOperand = stack.pop();
                    stack.push(leftOperand - rightOperand);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    int dividend = stack.pop();
                    stack.push(dividend / divisor);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
                    break;
            }
        }
        
        return stack.pop();
    }
}</integer>

Guia de Iteração em Estruturas de Dados Java

Durante a manipulação de arrays e coleções em problemas algorítmicos, é fundamental dominar as diferentes formas de iteração. Abaixo estão as abordagens mais eficientes e modernas no ecossistema Java.

Arrays e Strings

String text = "Algoritmo";
// Iteração sobre caracteres utilizando enhanced for-loop
for (char c : text.toCharArray()) {
    System.out.print(c + " ");
}

// Arrays multidimensionais
int[][] matrix = {{1, 2}, {3, 4}};
for (int[] row : matrix) {
    for (int value : row) {
        System.out.print(value + " ");
    }
}

Coleções (Listas e Mapas)

import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class IterationExamples {
    public static void main(String[] args) {
        List<string> frameworks = List.of("Spring", "Hibernate", "Micronaut");
        
        // Java 8+ forEach com Method Reference
        frameworks.forEach(System.out::println);

        Map<integer string=""> users = new HashMap<>();
        users.put(1, "Alice");
        users.put(2, "Bob");
        
        // Iteração em Mapas usando forEach com expressões lambda
        users.forEach((id, name) -> {
            System.out.println("ID: " + id + ", Nome: " + name);
        });
    }
}</integer></string>