class Solution {
    public int calculate(String str) {
        str = str.replace(" ","");
        LinkedList<String> list = new LinkedList<>();
        int index = 0;
        String store = "";
        while (index < str.length()){
            if( str.charAt(index) == '('){
                list.add(store);
                store = "";
            } else if ( str.charAt(index) == ')' ){
                String temp = compute(store);
                store = list.getLast() + temp;
                list.removeLast();
            } else {
                store += str.substring(index,index + 1 );
            }
            index++;
        }

        return Integer.parseInt(compute(store));
    }
    public static String compute(String str){
        class Word{
            Character op;
            Integer num;
            Word(Character op,Integer num){
                this.op = op;
                this.num = num;
            }
            
        }

        ArrayList<ArrayList<Word>> list = new ArrayList<>();
        int begin = 0;
        int end = 0;
        char op = '+';


        while (end < str.length()){
            if( op !=' '){
                while ( end < str.length() && ((str.charAt(end) <= '9' && str.charAt(end) >= '0') || (str.charAt(end) == '-' && begin == end) ) ){
                    end++;
                }
                if ( op == '+' || op == '-' ){
                    ArrayList<Word> ones = new ArrayList<>();
                    ones.add(new Word(op,Integer.parseInt(str.substring(begin,end))));
                    list.add(ones);
                    begin = end;
                } else if ( op == '*' || op == '/'){
                    list.get(list.size() - 1).add(new Word(op,Integer.parseInt(str.substring(begin,end))));
                    begin = end;
                }
                op = ' ';
            } else {
                end++;
                op = str.substring(begin,end).charAt(0);
                begin = end;
            }

        }
        ArrayList<Word> newList =  list.stream().map( l -> {
            Integer res = l.get(0).num;
            for (int i = 1; i < l.size(); i++) {
                if ( l.get(i).op == '*' ){
                    res = res * l.get(i).num;
                } else if ( l.get(i).op == '/' ){
                    res = res / l.get(i).num;
                }
            }
            return new Word(l.get(0).op, res);
        }).collect(Collectors.toCollection(ArrayList::new));
        Integer resNum = 0;
        for (int i = 0; i < newList.size(); i++) {
            if ( newList.get(i).op == '+' ){
                resNum = resNum + newList.get(i).num;
            } else if ( newList.get(i).op == '-' ){
                resNum = resNum - newList.get(i).num;
            }
        }
        
        return String.valueOf(resNum);
    }
}