Et si on calculait en 'Reverse Polish Notation'

Cette semaine, c'est Jordan qui vous propose un #KataOfTheWeek : RPN Calculator

Briefing du Kata : En notation polonaise inversée, les opérateurs suivent leurs opérandes ; par exemple, pour ajouter 3 et 4, on écrirait 3 4 + au lieu de 3 + 4. S'il y a plusieurs opérations, les opérateurs sont donnés immédiatement après leur deuxième opérande ; ainsi, l'expression écrite 3 - 4 + 5 en notation conventionnelle serait écrite 3 4 - 5 + en notation polonaise inversée : 4 est d'abord soustrait de 3, puis 5 y est ajouté. La notation polonaise inversée présente l'avantage de supprimer le recours aux parenthèses requises par la notation infixe. Alors que 3 - 4 × 5 peut également être écrit 3 - (4 × 5), cela signifie quelque chose de tout à fait différent de (3 - 4) × 5. En notation polonaise inversée, le premier pourrait être écrit 3 4 5 × -, ce qui signifie sans ambiguïté 3 (4 5 ×) - ce qui réduit à 3 20 - (qui peut encore être réduit à -17) ; ce dernier pourrait être écrit 3 4 - 5 × (ou 5 3 4 - ×, si le formatage utilisé est le même), ce qui signifie sans ambiguïté (3 4 -) 5 ×.

Plus d'information ici: https://en.wikipedia.org/wiki/Reverse_Polish_notation

Voici des exemples d'expressions :

• 1 => 1
• 1 2 + => (1 + 2) = 3
• 20 5 / => (20 / 5) = 4
• 4 2 + 3 - => (4 + 2) - 3 = 3
• 3 5 8 * 7 + * => 3*((5*8) + 7) = 141

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

Une des approches possible est de spliter la chaine, et boucler sur chacun des éléments, si on tombe sur un chiffre, on l'ajoute dans une pile, si on tombe sur un opérateur, alors on pop les deux derniers éléments ajoutés et les additionner, soustraire, multiplier ou diviser en fonction de ce dernier, puis mettre le résultat dans la pile, et on continue jusqu'à tomber sur le dernier opérateur et ainsi retourner le résultat final.

La solution peut être la suivante :

public class ReversePolishNotation {

    /**
     * Get the result of the RPN input.
     *
     * @param input the RPN
     * @return the result as Double
     */
    public static Double calc(String input) {
        Stack<Double> numbers = new Stack<>();
        Arrays.asList(input.split(" ")).stream().forEach(number -> {
            switch(number) {
                case "+":
                    calcSign(numbers, (n1, n2) -> n2 + n1);
                    break;
                case "-":
                    calcSign(numbers, (n1, n2) -> n2 - n1);
                    break;
                case "*":
                    calcSign(numbers, (n1, n2) -> n2 * n1);
                    break;
                case "/":
                    calcSign(numbers, (n1, n2) -> n2 / n1);
                    break;
                default:
                    numbers.push(Double.parseDouble(number));
            }
        });
        return numbers.pop();
    }

    /**
     * Insert the operation's result in the stack and return it.
     *
     * @param numbers the stack which contains all previously added numbers
     * @param operation the operation to apply on both last inserted number
     * @return the stack with the new added operation's result
     */
    static Stack<Double> calcSign(Stack<Double> numbers, BiFunction<Double, Double, Double> operation) {
        numbers.push(operation.apply(numbers.pop(), numbers.pop()));
        return numbers;
    }

}

Votre équipe TakiVeille