codility-word-stack-machine.java

Solution.java

import java.util.Stack;

/**
 * A word machine is a system that performs a sequence of simple operations
 * on a stack of integers. Initially the stack is empty. The sequence of
 * operations is given as a string. Operations are separated by single spaces.
 * The following operations may be specified:
 *
 *     - an integer X (between 0 and 2^20 - 1): the machine pushes X onto the stack;
 *     - "POP": the machine removes the topmost number from the stack;
 *     - "DUP": the machine pushes a duplicate of the topmost number onto the stack;
 *     - "+": the machine pops the topmost elements from the stack, adds them together
 *       and pushes the sum onto the stack;
 *     - "-": the machine pops the topmost elements from the stack, subtracts the second
 *       one from the first(topmost) one and pushes the difference onto the stack.
 *
 *  After processing all the operations, the machine returns the topmost
 *  value from the stack.
 *
 *  The machine processes 20-bit unsigned integers (numbers between 0 and 2^20-1).
 *  An overflow in addition or underflow in subtraction causes an error.
 *  The machine also reports an error when it tries to perform an operation
 *  that expects more numbers on the stack than the stack actually contains.
 *  Also, if, after performing all the operations, the stack is empty,
 *  the machine reports an error.
 *
 *  For example, given a string "13 DUP 4 POP 5 DUP + DUP + -", the machine
 *  performs the following operations:
 *
 *  operation | comment             | stack
 *  -----------------------------------------------------------------------
 *            |                     | [empty]
 *  "13"      | push 13             |
 *            |                     | 13
 *  "DUP"     | duplicate 13        |
 *            |                     | 13, 13
 *  "4"       | push 4              |
 *            |                     | 13, 13, 4
 *  "POP"     | pop 4               |
 *            |                     | 13, 13
 *  "5"       | push 5              |
 *            |                     | 13, 13, 5
 *  "DUP"     | duplicate 5         |
 *            |                     | 13, 13, 5, 5
 *  "+"       | adds 5 and 5        |
 *            |                     | 13, 13, 10
 *  "DUP"     | duplicate 10        |
 *            |                     | 13, 13, 10, 10
 *  "+"       | add 10 and 10       |
 *            |                     | 13, 13, 20
 *  "-"       | subtract 13 from 20 |
 *            |                     | 13, 7
 *
 * Finally, the machine will return 7.
 *
 * Given a string "5 6 + -", the machine reports an error, since an addition,
 * there is only one number on stack, but the subtraction operation expects
 * two.
 *
 * Given a string "3 DUP 5 - -", the machine reports an error, since the
 * second subtraction yields a negative result.
 *
 * Write a function:
 *     class Solution { public int solution(String S); }
 *
 * that, given a string S containing a sequence of operations for the word
 * machine, returns the result the machine would return after processing
 * the operations. The function should return -1 if the machine would report
 * an error while processing the operations.
 *
 * For example, given string S = "13 DUP 4 POP 5 DUP + DUP + -" the function
 * should return 7, as explained in the example above. Given string
 * S="5 6 + -" or S="3 DUP 5 - -" the function should return -1.
 *
 * Assume that:
 *     - the length of S is within the range [0 .. 2,000];
 *     - S is a valid sequence of word machine operations.
 *
 *  In your solution, focus on correctness. The performance of your solution
 *  will not be focus of the assessment.
 */
class Solution {
    public int solution(String S) {
        try {
            return solutionInternal(S);
        } catch(Exception e) {
            return -1;
        }
    }

    private static final int MAX_VALUE = (1<<20) - 1;

    private int solutionInternal(String S) {
        Stack<Integer> stack = new Stack<Integer>();
        String[] insns = S.split(" ");
        for(String insn : insns) {
            if (insn.matches("[0-9]+")) {
                int value = Integer.parseInt(insn);
                if (value < 0 || value > MAX_VALUE) { // over/underflow
                    return -1;
                }
                stack.push(value);
                //System.out.print("push " + value);
            } else if ("DUP".equals(insn)) {
                int value = stack.peek();
                stack.push(value);
                //System.out.print("duplicate " + value);
            } else if ("POP".equals(insn)) {
                int value = stack.pop();
                //System.out.print("pop " + value);
            } else if ("+".equals(insn)) {
                int a = stack.pop();
                int b = stack.pop();
                if (a + b > MAX_VALUE) {  // overflow
                    return -1;
                }
                stack.push(a + b);
                //System.out.print("add " + a + " and " + b);
            } else if ("-".equals(insn)) {
                int a = stack.pop();
                int b = stack.pop();
                if (a - b < 0) { // underflow
                    return -1;
                }
                stack.push(a - b);
                //System.out.print("subtract " + b + " from " + a);
            } else {
                throw new IllegalArgumentException("Unknown operation: " + insn);
            }

            //System.out.println(Arrays.toString(stack.toArray()));
        }

        return stack.pop();
    }

    // main, test() 는 Codility에서 사용하지 않음
    public static void main(String[] args) {
        test("13 DUP 4 POP 5 DUP + DUP + -", 7);
        test("5 6 + -", -1);
        test("3 DUP 5 - -", -1);
        test("13", 13);
        test("524288 524288 +", -1);  // overflow test
        test("524288 524287 +", 1048575);
        test("524288 524288 0 - -", -1);  // underflow test
    }

    private static void test(String S, int expected) {
        int actual = new Solution().solution(S);
        if (expected == actual) {
            System.out.print("[+] ");
        } else {
            System.out.print("[-] ");
        }
        System.out.printf("%s: expected=%d, actual=%d\n", S, expected, actual);
    }
}