## DEV Community is a community of 617,782 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Advent of Code 2020 Solution Megathread - Day 18: Operation Order Ervin Szilagyi • Edited

Today's problem is the perfect candidate for using a recursive divide-and-conquer approach

Basically what I did is to solve the innermost expressions in the parenthesis and use this partial result to solve the outer expressions recursively. In case of part two, it is a bit trickier, since there is operator precedence. In this case when I encountered a multiplication, I've split the expression in 2 parts, basically solving the additions first and applying the multiplications afterwards for the partial results.

Here is my code in Java. It's a bit hefty, because Java, but it does the job:

``````public interface Day18 {
Pattern pattern = Pattern.compile("[0-9]+");

static long part1(List<String> lines) {
return lines.stream()
.map(Day18::splitLine)
.mapToLong(Day18::solveExpressionSameOperationPrecedence)
.sum();
}

static long part2(List<String> lines) {
return lines.stream()
.map(Day18::splitLine)
.sum();
}

private static List<String> splitLine(String line) {
List<String> parts = new ArrayList<>();
for (String part : line.split(" ")) {
if (part.charAt(0) == '(' || part.charAt(part.length() - 1) == ')') {
Matcher matcher = pattern.matcher(part);
String number = "";
if (matcher.find()) {
number = matcher.group(0);
}
String brackets = part.replaceFirst(number, "");
if (part.charAt(0) == '(') {
for (char c : brackets.toCharArray()) {
}
} else {
for (char c : brackets.toCharArray()) {
}
}
continue;
}
}
return parts;
}

private static long solveExpressionSameOperationPrecedence(List<String> expression) {
long result = 0;
int i = 0;
while (i < expression.size()) {
String part = expression.get(i);

if (pattern.matcher(part).matches()) {
long value = Long.parseLong(part);
result = operation.apply(result, value);
i++;
continue;
}

if (part.equals("(")) {
List<String> subEquation = extractSubExpression(expression, i);
result = operation.apply(result, solveExpressionSameOperationPrecedence(subEquation));
i += subEquation.size() + 2;
continue;
}

operation = Operation.fromString(part);
i++;
}
return result;
}

private static long solveExpressionAdditionPrecedence(List<String> expression) {
long result = 0;
int i = 0;
while (i < expression.size()) {
String part = expression.get(i);

if (pattern.matcher(part).matches()) {
i++;
continue;
}

if (part.equals("(")) {
List<String> subExpression = extractSubExpression(expression, i);
i += subExpression.size() + 2;
continue;
}

if (Operation.fromString(part) == Operation.MULTIPLY) {
result = Operation.MULTIPLY.apply(result, solveExpressionAdditionPrecedence(expression.subList(i + 1, expression.size())));
break;
}
i++;
}
return result;
}

private static List<String> extractSubExpression(List<String> expression, int index) {
int openBrackets = 1;
int i = index + 1;
for (; i < expression.size() && openBrackets > 0; i++) {
String nextPart = expression.get(i);
if (nextPart.equals("(")) {
openBrackets++;
continue;
}
if (nextPart.equals(")")) {
openBrackets--;
}
}
return expression.subList(index + 1, i - 1);
}
}

enum Operation {
public long apply(long a, long b) {
return a + b;
}
},
MULTIPLY {
public long apply(long a, long b) {
return a * b;
}
};

public static Operation fromString(String operation) {
if (operation.equals("+")) {