class Solution {

    public int calculate(String s) {
        return calculate(s.toCharArray(), 0, s.length() - 1);
    }

    private int calculate(char[] s, int l, int r) {
        char lastOp = '.';
        final NumberHolder current = new NumberHolder();
        final NumberHolder prevPrev = new NumberHolder();
        final NumberHolder prev = new NumberHolder();

        for (int i = l; i <= r; i++) {
            final char c = s[i];
            final boolean isDigit = c >= '0' && c <= '9';

            if (c == '(') {
                int pCount = 1;
                int expEnd;
                for (expEnd = i + 1; expEnd <= r; expEnd++) {
                    if (s[expEnd] == '(') {
                        pCount++;
                    } else if (s[expEnd] == ')') {
                        pCount--;
                    }
                    if (pCount == 0) {
                        break;
                    }
                }
                current.setValue(calculate(s, i + 1, expEnd - 1));
                i = expEnd;

            } else if (isDigit) {
                current.setValue(current.value * 10 + (c - '0'));
            }

            if (current.hasValue && (!isDigit || i == r)) {
                final int newNumber = lastOp == '-' ? -current.value : current.value;
                current.clear();
                if (lastOp == '*' || lastOp == '/') {
                    if (lastOp == '*') {
                        prev.setValue(prev.value * newNumber);
                    } else {
                        prev.setValue(prev.value / newNumber);
                    }
                } else if ((lastOp == '+' || lastOp == '-') && prev.hasValue && prevPrev.hasValue) {
                    prevPrev.setValue(prevPrev.value + prev.value);
                    prev.setValue(newNumber);
                } else {
                    if (prev.hasValue) {
                        prevPrev.setValue(prev.value);
                    }
                    prev.setValue(newNumber);
                }
            }

            if (c == '+' || c == '-' || c == '*' || c == '/') {
                lastOp = c;
            }
        }

        return prev.value + prevPrev.value;
    }

    private static class NumberHolder {
        int value;
        boolean hasValue = false;

        public void setValue(int v) {
            value = v;
            hasValue = true;
        }

        public void clear() {
            value = 0;
            hasValue = false;
        }
    }
}