Visitor: Expression Tree

/*
 * Problem : Print and evaluate a tree.
 * Input   : One postfix expression.
 * Output  : Text, then value.
 * Approach: Visitor pattern.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A visitor has one method for each kind of node. The result type R is the answer of the visitor.
        interface Visitor<R> {
            R visitNumber(long value);

            R visitOperation(char operator, Node left, Node right);
        }

        // Step 2: Nodes only know how to accept a visitor. They do not know what the visitor does.
        interface Node {
            <R> R accept(Visitor<R> visitor);
        }

        static class NumberNode implements Node {
            final long value;

            NumberNode(long value) {
                this.value = value;
            }

            public <R> R accept(Visitor<R> visitor) {
                return visitor.visitNumber(value);
            }
        }

        static class OperationNode implements Node {
            final char operator;
            final Node left;
            final Node right;

            OperationNode(char operator, Node left, Node right) {
                this.operator = operator;
                this.left = left;
                this.right = right;
            }

            public <R> R accept(Visitor<R> visitor) {
                return visitor.visitOperation(operator, left, right);
            }
        }

        // Step 3: Two visitors, two jobs. Adding a third job means adding a third visitor, and the nodes stay unchanged.
        static class PrintVisitor implements Visitor<String> {
            public String visitNumber(long value) {
                return String.valueOf(value);
            }

            public String visitOperation(char operator, Node left, Node right) {
                return "(" + left.accept(this) + " " + operator + " " + right.accept(this) + ")";
            }
        }

        static class EvaluateVisitor implements Visitor<Long> {
            public Long visitNumber(long value) {
                return value;
            }

            public Long visitOperation(char operator, Node left, Node right) {
                long a = left.accept(this);
                long b = right.accept(this);
                return operator == '+' ? a + b : operator == '-' ? a - b : a * b;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        // Step 4: Build the tree from the postfix tokens with a stack.
        java.util.ArrayDeque<Node> stack = new java.util.ArrayDeque<Node>();
        for (String token : s.trim().split("\\s+")) {
            if (token.length() == 1 && "+-*".indexOf(token.charAt(0)) >= 0) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new OperationNode(token.charAt(0), left, right));
            } else {
                stack.push(new NumberNode(Long.parseLong(token)));
            }
        }
        Node root = stack.pop();
        return new String[] {root.accept(new PrintVisitor()), String.valueOf(root.accept(new EvaluateVisitor()))};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}