Iterative (non-recursive) implementation for aggregating Items of a List of List with arbitrary depth

Give an array such as:

[4, 2, [6, -4], 1, [3, [-13, 7], 2]]

I expect the see the number -15 as based on the depth of the array determines its multiplier e.g.

4 + 2 + 2(6 + -4) + 1 + 2(3 + 3(-13 + 7) + 2)

I have solved this recursively as below, But how would I achieve this iteratively?

This is the recursive solution:-

class Calculator {

    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;
    }

    public static void main(String[] args) {

        List<Object> list = new ArrayList<Object>();
        list.add(4);
        list.add(2);
        List<Object> objs = new ArrayList<Object>();
        objs.add(6);
        objs.add(-4);
        list.add(objs);
        list.add(1);
        List<Object> objs2 = new ArrayList<Object>();
        objs2.add(3);
        List<Object> objs3 = new ArrayList<Object>();
        objs3.add(-13);
        objs3.add(7);
        objs2.add(objs3);
        objs2.add(2);
        list.add(objs2);

        int res = Calculator.calc(list);
        
        System.out.println(res);
    }
}

</details>


# 答案1
**得分**: 2

也许是这样的：

```java
Function<List<?>, Double> aggregator = list -> {
    Double value = 0.0;
    int depth = 1;
    double factor = 1;
    while (!list.isEmpty()) {
        List<?> remainingLevels = new ArrayList<>();
        for (Object item : list) {
            if (item instanceof Double) {
                // 加入数字
                value += factor * (Double) item;
            } else if (item instanceof List) {
                // 加入元素，移除一层
                remainingLevels.addAll((List) item);
            } else {
                throw new IllegalArgumentException();
            }
        }
        depth++;
        factor *= depth;
        list = remainingLevels;
    }
    return value;
};

注意：我更喜欢递归解决方案！

Function<List<?>,Double> aggregator = list -> {
	Double value = 0.0;
	int depth = 1;
	double factor = 1;
	while(!list.isEmpty()) {
		List<?> remainingLevels = new ArrayList<>();
		for(Object item : list) {
			if(item instanceof Double) {
				// Add number
				value += factor * (Double)item;
			}
			else if(item instanceof List) {
				// Add elements, removing one level
				remainingLevels.addAll((List)item);
			}
			else {
				throw new IllegalArgumentException();
			}
		}
		depth++;
		factor *= depth;
		list = remainingLevels;
	}
	return value;
};

答案2

得分: 2

我喜欢堆栈，所以这里有一个替代方案，它使用Boolean作为信号来增加或减少深度。

int sum = 0, depth = 1, multiplier = 1;

Stack stack = new Stack();
stack.addAll(list);

while (!stack.isEmpty()) {
  Object next = stack.pop();

  if (next instanceof Collection) {
    stack.add(false); //False 表示向外移动
    stack.addAll((Collection) next);
    stack.add(true); //True 表示向内移动
  } else if (next instanceof Boolean) {
    if ((Boolean) next)
      multiplier *= ++depth;
    else 
      multiplier /= depth--;
  } else sum += multiplier * (Integer) next;
}

return sum;

int sum = 0, depth = 1, multiplier = 1;

Stack stack = new Stack();
stack.addAll(list);

while (!stack.isEmpty()) {
  Object next = stack.pop();

  if (next instanceof Collection) {
    stack.add(false); //False means moving out
    stack.addAll((Collection) next);
    stack.add(true); //True means moving in
  } else if (next instanceof Boolean) {
    if ((Boolean) next)
      multiplier *= ++depth;
    else 
      multiplier /= depth--;
  } else sum += multiplier * (Integer) next;
}

return sum;