import java.util.*;

public class Calc {

    public static final int ADD = 0, SUBTRACT = 1, MULTIPLY = 2, DIVIDE = 3,
                            POWER = 4, LOG = 5, SIN = 6, COS = 7, TAN = 8,
                            SQRT = 9, PI = 10, EULER = 11, NUMBER = 12;
    public static final String[] token_map = {"+", "-", "*", "/", "^", "ln", "sin",
                                              "cos", "tan", "sqrt", "pi", "e"};

    public static class StringToken {

        public int instruction;
        public String subtoken0;
        public String subtoken1;

        public StringToken(int inst, String subt0, String subt1) {
            this.instruction = inst;
            this.subtoken0 = subt0;
            this.subtoken1 = subt1;
        }

    }

    public static class Token {

        private List<Token> subtokens = new LinkedList();
        private int instruction;
        private double value;

        public Token(int inst) {
            this.value = 0;
            this.instruction = inst;
        }

        public void set_instruction(int inst) {
            this.instruction = inst;
        }

        public boolean insert(double value) {
            if (this.instruction == 12) {
                this.value = value;
                return true;
            } else {
                return false;
            }
        }

        public boolean insert(Token subtoken) {
            if (this.instruction < 12) {
                this.subtokens.add(subtoken);
                return true;
            } else {
                return false;
            }
        }

        public double evaluate() {
            switch (this.instruction) {
            case Calc.NUMBER:
                return this.value;
            case Calc.EULER:
                return Math.E;
            case Calc.PI:
                return Math.PI;
            case Calc.SQRT:
                return Math.sqrt(this.subtokens.get(0).evaluate());
            case Calc.POWER:
                return Math.pow(this.subtokens.get(0).evaluate(), this.subtokens.get(1).evaluate());
            case Calc.MULTIPLY:
                return this.subtokens.get(0).evaluate() * this.subtokens.get(1).evaluate();
            case Calc.DIVIDE:
                return this.subtokens.get(0).evaluate() / this.subtokens.get(1).evaluate();
            case Calc.ADD:
                return this.subtokens.get(0).evaluate() + this.subtokens.get(1).evaluate();
            case Calc.SUBTRACT:
                return this.subtokens.get(0).evaluate() - this.subtokens.get(1).evaluate();
            case Calc.SIN:
                return Math.sin(this.subtokens.get(0).evaluate());
            case Calc.COS:
                return Math.cos(this.subtokens.get(0).evaluate());
            case Calc.TAN:
                return Math.tan(this.subtokens.get(0).evaluate());
            case Calc.LOG:
                return Math.log(this.subtokens.get(0).evaluate()) / Math.log(Math.E);
            default:
                return Double.NaN;
            }
        }
    }

    public static double evaluate(Token master_token) {
        return master_token.evaluate();
    }

    public static Token combine(Token master, StringToken subtoken) {
        if (subtoken.instruction == 12) {
            master.set_instruction(12);
            master.insert(Integer.parseInt(subtoken.subtoken0));
        } else if (subtoken.instruction == -1) {

        } else {
            master.set_instruction(subtoken.instruction);
            master.insert(parse_string(subtoken.subtoken0));
            master.insert(parse_string(subtoken.subtoken1));
        }
        return master;
    }

    public static Token parse_string(String expression) {
        Token master = new Token(-1);
        master = combine(master, lowest_token(expression));
        return master;
    }

    public static String join_list(List<String> list) {

        String output = "";
        for (int i = 0;i < list.size();i++) {
            output += list.get(i);
        }
        return output;
    }

    public static int index_of(List<String> list, String comp) {
        for (int i = 0;i < list.size();i++) {
            if (list.get(i).equals(comp))
                return i;
        }
        return -1;
    }

    public static StringToken lowest_token(String expression) {

        if (expression.length() == 0)
            return new StringToken(-1, "", "");
        else if (expression.startsWith("(") && expression.endsWith(")"))
            expression = (String) expression.subSequence(1, expression.length() - 1);
        int lbrackets, rbrackets;
        String[] tokenarray = expression.split(
                "(?<=(ln)|(sin)|(cos)|(tan)|(fac)|(pi)|(e)|\\(|\\)|\\^|/|\\*|\\+|\\-|\\.|\\d)"
                );
        List<String> tokenlist = new LinkedList<String>();
        for (int i = 0;i < tokenarray.length;i++) {
            tokenlist.add(tokenarray[i]);
        }
        StringToken master_token = new StringToken(-1, "", "");

        for (int i = 0;i < 13;i++) {
            if (i == 12) {
                master_token.instruction = 12;
                master_token.subtoken0 = join_list(tokenlist);
                return master_token;
            } else if (!tokenlist.contains(token_map[i])) {
                continue;
            }
            for (int c = 0;c < tokenlist.size();c++) {
                if (tokenlist.indexOf(token_map[i]) == c) {
                    lbrackets = 0;
                    rbrackets = 0;
                    for (int x = 0;x < c;x++) {
                        if (tokenlist.get(x).equals("("))
                            lbrackets++;
                        else if (tokenlist.get(x).equals(")"))
                            rbrackets++;
                    }
                    if (lbrackets == rbrackets) {
                        master_token.instruction = i;
                        if (i < 5) {
                            master_token.subtoken0 = join_list(tokenlist.subList(0, c));
                            master_token.subtoken1 = join_list(tokenlist.subList(c+1, tokenlist.size()));
                        } else {
                            lbrackets = 0;
                            rbrackets = 0;
                            for (int x = c + 1;x < tokenlist.size();x++) {
                                if (tokenlist.get(x).equals("("))
                                    lbrackets++;
                                else if (tokenlist.get(x).equals(")"))
                                    rbrackets++;
                                if (lbrackets == rbrackets) {
                                    master_token.subtoken0 = join_list(tokenlist.subList(c + 2, x));
                                    break;
                                }
                            }
                        }
                        return master_token;
                    }
                }
            }
        }
        return new StringToken(-1, "", "");
    }

    public static double evaluate(String expression) {
        return evaluate(parse_string(expression));
    }

    public static void main(String[] args) {
        // Input: ln(sin(3^5*2)/(10+3))
        String expression = "ln(sin(3^5*2)/(10+3))";
        System.out.println(evaluate(expression));
        // Output: -2.7737145543097883 (correct)
    }

}