Recursive Java solution with stack


  • 0
    A

    The main idea is that every time encountering a '(', go into recursion to calculate the nested result and then if encountering a ')', return the nested result to outside.

    The drawback compared to iterative way with stack is that I use more space but in the same magnitude, constant space complexity.

    Here is my code.

    public class Solution {
        public int calculate(String s) {
            if (s == null || s.length() == 0) return 0;
            Stack<Character> stack = new Stack<Character>();
            for (int i = s.length()- 1; i >= 0; i --) stack.push(s.charAt(i));
            return cal(stack);
        }
        private int cal(Stack<Character> stack) {
            int result = 0, number = 0, sign = 1;
            while(!stack.isEmpty()) {
                char ch = stack.pop();
                if (ch >= '0' && ch <= '9') {
                    number = 10 * number + ch - '0';
                } else if (ch == '+') {
                    result += sign * number;
                    number = 0;
                    sign = 1;
                } else if (ch == '-') {
                    result += sign * number;
                    number = 0;
                    sign = -1;
                } else if (ch == '(') {
                    number = cal(stack);
                } else if (ch == ')') {
                    result += sign * number;
                    return result;
                }
            }
            if (number != 0) result += sign * number;
            return result;
        }
    }
    

Log in to reply
 

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