public class PrefixEvaluator {
    public static void main(String[] args) {
        String input = "(+(+23)(+41))";
        // String input = "(1+(+23)(+41))";
        // String input = "(++(+23)(+41))";
        System.out.println(calculate(input));
    }

    public static int calculate(String str) {
        // because prefix doesn't need parenthesses
        String clean = str.replaceAll("[()]", ""); // regex: [] = charset
        Stack<Integer> stc = new Stack<>();

        // because prefix, reverse the eval seq
        for (int i = clean.length() - 1; i >= 0; i--) {
            char c = clean.charAt(i);
            if (c == '+') {
                if (stc.size() < 2) {
                    throw new IllegalArgumentException("Invalid expression");
                }
                stc.push(stc.pop() + stc.pop());
            } else {
                stc.push(Character.getNumericValue(c));
            }
        }

        if (stc.size() != 1) {
            throw new IllegalArgumentException("Invalid expression");
        }

        return stc.pop();
    }
}