import java.util.LinkedList;

/**
 * A <i>stack machine</i> is a simple system that performs arithmetic operations
 * on an input string of numbers and operators. It contains a stack that
 * can store an arbitrary number of 12-bit unsigned integers. Initially the
 * stack is empty. The machine processes a string of characters in the
 * following way:<br/><br/>
 *
 * - the characters of the string are processed one by one;<br/>
 * - if the current character is a digit ('0'-'9'), the machine
 * pushes the value of that digit onto its stack;<br/>
 * - if the current character is '+', the machine pops the two
 * topmost values from its stack, adds them and pushes the result
 * onto the stack;<br/>
 * - if the current character is '*', the machine pops the two
 * topmost values from its stack, multiplies them and pushes the
 * result onto the stack;<br/>
 * - after the machine has processed the whole string it returns the
 * topmost value of its stack as the result;<br/>
 * - the machine reports an error if any operation it performs
 * (addition or multiplication) results in an overflow;<br/>
 * - the machine reports an error if it tries to pop an element from
 * its stack when the stack is empty, or if the stack is empty
 * after the machine has processed the whole string.<br/><br/>
 *
 * For example, given the string "13+62*7+*" the machine will perform the
 * following operations:<br/><br/>
 *
 * <pre>{@code
 *
 *  character | comment                | stack
 * -----------------------------------------------
 *            |                        | [empty]
 * '1'        | push 1 onto the stack  |
 *            |                        | 1
 * '3'        | push 3 onto the stack  |
 *            |                        | 1, 3
 * '+'        | perform addition       |
 *            |                        | 4
 * '6'        | push 6 onto the stack  |
 *            |                        | 4, 6
 * '2'        | push 2 onto the stack  |
 *            |                        | 4, 6, 2
 * '*'        | perform multiplication |
 *            |                        | 4, 12
 * '7'        | push 7 onto the stack  |
 *            |                        | 4, 12, 7
 * '+'        | perform addition       |
 *            |                        | 4, 19
 * '*'        | perform multiplication |
 *            |                        | 76
 * }</pre>
 *
 * The machine will return 76 as the result as it is the topmost element of
 * its stack.<br/><br/>
 *
 * Write a function:<br/>
 *
 * {@code
 * 		class Solution { public int solution(string S); }
 * }<br/><br/>
 *
 * that, given a string S consisting of N characters containing input for
 * the stack machine, returns the result the machine would return if given
 * this string. The function should return −1 if the machine would report
 * an error when processing the string.<br/><br/>
 *
 * For example, given string S = "13+62*7+*" the function should return 76,
 * as explained in the example above. Given string S = "11++" the function
 * should return −1.<br/><br/>
 *
 * Assume that:<br/>
 * - the length of S is within the range [0..200,000];<br/>
 * - string S consists only of the following characters: "0", "1",
 * "2", "3", "4", "5", "6", "7", "8", "9", "+" and/or "*".<br/><br/>
 *
 * In your solution, focus on **correctness**. The performance of your
 * solution will not be the focus of the assessment.<br/><br/>
 *
 */
public class StackMachine {

    public static void main(String[] args) {
        System.out.println("Expected solution: 76");
        System.out.println("Actual solution: " + getSolution("13+62*7+*"));
    }



	public static int getSolution(String s) {
		LinkedList<Integer> stack = new LinkedList(); // 'Stack' would be a good class as well

		if (s == null || s.length() == 0)
			return -1;

		for (int n=0; n<s.length(); ++n) {
			char c = s.charAt(n);

			if (c >= '0' && c <= '9') { // Check whether the char represents a digit
				stack.push(c - '0'); // Convert from char to int
			} else if (stack.size() >= 2) { // There must be at least two entries on the stack in order to start operating
				if (c == '+') {
					int x = stack.pop() + stack.pop();
					if (x < 4096) // The stack entry cannot be bigger than 12-bit
						stack.push(x);
					else return -1;
				} else if (c == '*') {
					int x = stack.pop() * stack.pop();
					if (x < 4096)
						stack.push(x);
					else return -1;
				} else return -1;
			} else return -1;
		}

		return stack.peek();
	}

}