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;