// ----------------
// PostfixEval.java
// ----------------

import java.util.Stack;
import java.util.StringTokenizer;

final class PostfixEval {
    /**
     * 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) {
        final StringTokenizer st = new StringTokenizer(s);
        final Stack<Long>     sl = new Stack<Long>();
        while (st.hasMoreTokens()) {
            final String t = st.nextToken();
            final char   c = t.charAt(0);
            switch (c) {
                case '+': {
                    final long v = sl.pop();
                    final long w = sl.pop();
                    sl.push(w + v);
                    break;}
                case '-': {
                    final long v = sl.pop();
                    final long w = sl.pop();
                    sl.push(w - v);
                    break;}
                case '*': {
                    final long v = sl.pop();
                    final long w = sl.pop();
                    sl.push(w * v);
                    break;}
                default:
                    sl.push(Long.parseLong(t));}}
        return sl.pop();}}

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

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

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