Java recursive method, intuitive and easy to understand


  • 0

    Idea: The program performs what exactly goes on in human mind when we do such calculations. We basically iterate through the string, progressively calculate the subresults step by step, and when we encounter a left parenthesis, we recursively call the method to get the result inside, append it to the current result, and we will get the final answer.

    Also, this method supports negative integers.

    Code:

    public class Solution {
        public int calculate(String s) {
            Map<Integer, Integer> map = new HashMap<>();
            Stack<Integer> stack = new Stack<>();
            
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') stack.push(i);
                if (s.charAt(i) == ')') map.put(stack.pop(), i);
            }
            
            return calculate(s, 0, s.length() - 1, map);
        }
        
        private int calculate(String s, int start, int end, Map<Integer, Integer> map) {
            if (start > end || end < 0 || start > s.length() - 1) return 0;
            
            int result = 0;
            int sign = 1;
            
            for (int i = start; i <= end; i++) {
                if (s.charAt(i) == '(') return result + sign * calculate(s, i + 1, map.get(i) - 1, map) + calculate(s, map.get(i) + 1, end, map);
                
                if (Character.isDigit(s.charAt(i))) {
                    int curr = 0;
                    int j = i;
                    while (j <= end && Character.isDigit(s.charAt(j))) curr = curr * 10 + s.charAt(j++) - '0';
                    i = j - 1;
                    result += curr * sign;
                } else if (s.charAt(i) == '+') {
                    sign = 1;
                } else if (s.charAt(i) == '-') {
                    sign = -1;
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.