// ---------------
// PrefixEval.java
// ---------------

import java.util.StringTokenizer;

final class PrefixEval {
    /**
     * O(n) in space
     * O(n) in time
     */
    private static long eval (StringTokenizer st) {
        final String t = st.nextToken();
        final char   c = t.charAt(0);
        switch (c) {
            case '+':
                return eval(st) + eval(st);
            case '-':
                return eval(st) - eval(st);
            case '*':
                return eval(st) * eval(st);
            default:
                return Long.parseLong(t);}}

    /**
     * O(n) in space
     * O(n) in time
     * Precondition: s.length() > 0
     * Precondition: ((s.charAt(i) >= '0') && (s.charAt(i) <= '9')) || (s.charAt(i) == '[ +-*]')
     * expr -> + expr expr
     *      |  - expr expr
     *      |  * expr expr
     *      |  number
     */
    public static long eval (String s) {
        return eval(new StringTokenizer(s));}}

final class PrefixEvalTest {
    public static void main (String[] args) {
        System.out.println("PrefixEval.java");

        assert PrefixEval.eval("2")             ==   2;
        assert PrefixEval.eval("+ 2 3")         ==   5;
        assert PrefixEval.eval("- 2 3")         ==  -1;
        assert PrefixEval.eval("* 2 3")         ==   6;
        assert PrefixEval.eval("+ - * 2 3 4 5") ==   7;
        assert PrefixEval.eval("+ 2 - 3 * 4 5") == -15;
        assert PrefixEval.eval("+ 23 45")       ==  68;

        System.out.println("Done.");}}