如何迭代实现带深度乘数的任意嵌套列表元素聚合计算？

Great question! Converting recursive depth-based calculations to an iterative approach requires manually simulating the call stack that recursion uses under the hood. Let's walk through how to do this for your depth-weighted sum problem.

Core Idea #

Recursion automatically tracks the current list and its depth, plus the ongoing sum for each level. For iteration, we'll use a stack to store state objects that keep track of:

• The list we're processing
• Its current depth
• The sum we've accumulated so far for this list
• An iterator to track which element of the list we're on

This lets us pause processing a parent list to handle its child lists first (just like recursion does), then resume the parent once the child's contribution is calculated.

Iterative Java Implementation #

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

class Calculator {
    // Helper class to hold the state of each list being processed
    private static class ListState {
        List<Object> list;
        int depth;
        int currentSum;
        Iterator<Object> iterator;

        ListState(List<Object> list, int depth) {
            this.list = list;
            this.depth = depth;
            this.currentSum = 0;
            this.iterator = list.iterator();
        }
    }

    public static int calcIterative(List<Object> array) {
        Stack<ListState> stack = new Stack<>();
        stack.push(new ListState(array, 1));
        int result = 0;

        while (!stack.isEmpty()) {
            ListState currentState = stack.peek();

            if (currentState.iterator.hasNext()) {
                Object item = currentState.iterator.next();
                if (item instanceof List) {
                    // Pause current list, push child list to stack to process first
                    stack.push(new ListState((List<Object>) item, currentState.depth + 1));
                } else {
                    // Add number to current list's sum
                    currentState.currentSum += (int) item;
                }
            } else {
                // Finished processing current list: calculate its contribution
                int contribution = currentState.depth * currentState.currentSum;
                stack.pop();

                if (!stack.isEmpty()) {
                    // Add contribution to parent list's sum
                    stack.peek().currentSum += contribution;
                } else {
                    // This is the root list, set as final result
                    result = contribution;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // Build the test array
        List<Object> list = new ArrayList<>();
        list.add(4);
        list.add(2);
        List<Object> objs = new ArrayList<>();
        objs.add(6);
        objs.add(-4);
        list.add(objs);
        list.add(1);
        List<Object> objs2 = new ArrayList<>();
        objs2.add(3);
        List<Object> objs3 = new ArrayList<>();
        objs3.add(-13);
        objs3.add(7);
        objs2.add(objs3);
        objs2.add(2);
        list.add(objs2);

        // Test iterative solution
        int resIterative = Calculator.calcIterative(list);
        System.out.println("Iterative result: " + resIterative); // Should output -15

        // Compare with recursive result
        int resRecursive = Calculator.calc(list);
        System.out.println("Recursive result: " + resRecursive); // Should output -15
    }

    // Keep your original recursive method here for comparison
    public static int calc(List<Object> array) {
        return calc(array, 1);
    }
    public static int calc(List<Object> array, int depth) {
        int sum = 0;
        for (Object object : array) {
            if (object instanceof ArrayList) {
                sum += calc((List<Object>) object, (depth + 1));
            } else {
                sum += (int) object;
            }
        }
        return depth * sum;
    }
}

How It Works #

Let's break down the key steps with your example array [4, 2, [6, -4], 1, [3, [-13, 7], 2]]:

1. Initialize the stack with the root list and depth 1.
2. Process each element:
   • For numbers like 4 and 2, we add them directly to the current list's currentSum.
   • When we hit a sublist like [6, -4], we push the current list's state back to the stack, then push the sublist with depth 2 to start processing it.
3. Finish a list:
   • Once we've processed all elements of a sublist (like [6, -4]), we calculate its contribution: 2 * (6 + -4) = 4.
   • We pop this sublist's state from the stack and add the contribution to the parent list's currentSum.
4. Final calculation: When we finish processing the root list, its contribution is the final result: 1 * (4 + 2 + 4 + 1 + 2*(3 + 3*(-13+7)+2)) = -15.

This approach perfectly mimics the recursive logic but uses an explicit stack instead of the call stack, making it iterative.

内容的提问来源于stack exchange，提问作者maggic