## 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 Ryan Palo • Edited

Here's my solution. Doesn't quite support arbitrary levels of precedence, but we only needed two max, and that's what it works for. I'm comfortable with the knowledge that I could probably have put together an arbitrary precedence interpreter together if I had needed to. 😁

``````#include "Day18.h"

#include <stdio.h>

#include "parsing.h"

/// Day 18: Operation Order
///
/// Parse math expressions with different precedence rules than normal.

#define MAX_TOKENS 100  ///< Maximum number of tokens in a line

/// The different tokens our parser might encounter
typedef enum {
TOK_NULL,         ///< A placeholder token to represent {0}
TOK_NUM,          ///< A digit 0-9 (no double-digits in input)
TOK_OPEN_PAREN,   ///< (
TOK_CLOSE_PAREN,  ///< )
TOK_PLUS,         ///< +
TOK_STAR,         ///< *
TOK_END,          ///< End of line sentinel
} TokenType;

const char* token_type[] = {"Null", "Num", "Open Paren", "Close Paren", "Plus", "Star", "End"};

/// A Token is essentially just a TokenType, but NUM tokens can store their value
typedef struct {
TokenType type;
long val;
} Token;

/// An iteratable of Tokens, that can be consumed and used up
/// but is also really just a list of Tokens with a memory
typedef struct {
Token* tokens;
Token* current;
} TokenIter;

/// Parse a line of input into a TokenIter
TokenIter parse_line(FILE* fp) {
Token* tokens = (Token*)malloc(sizeof(Token) * MAX_TOKENS);
int i = 0;
char c;
while ((c = getc(fp)) != EOF) {
switch (c) {
case '0' ... '9':
tokens[i].type = TOK_NUM;
tokens[i].val = c - '0';
break;
case '(': tokens[i].type = TOK_OPEN_PAREN; break;
case ')': tokens[i].type = TOK_CLOSE_PAREN; break;
case '+': tokens[i].type = TOK_PLUS; break;
case '*': tokens[i].type = TOK_STAR; break;
case '\n':
tokens[i].type = TOK_END;
return (TokenIter){
.tokens = tokens,
.current = NULL,
};
case ' ': continue;
default: printf("Bad char %c.\n", c); exit(EXIT_FAILURE);
}
i++;
}

// May encounter end of file without newline
tokens[i].type = TOK_END;
return (TokenIter){
.tokens = tokens,
.current = NULL,
};
}

/// Parse input file so that each line is an iter of Tokens
TokenIter* parse(const char* filename, int* count) {
FILE* fp;
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Couldn't open input file.\n");
exit(EXIT_FAILURE);
}

*count = count_lines(fp);
TokenIter* lines = (TokenIter*)malloc(sizeof(TokenIter) * *count);

for (int i = 0; i < *count; i++) {
lines[i] = parse_line(fp);
}

fclose(fp);
return lines;
}

/// Iterate to next token (or prime the pump on a fresh iterable)
Token* token_next(TokenIter* iter) {
if (iter->current == NULL) {
iter->current = iter->tokens;
return iter->current;
}
if (iter->current->type == TOK_END) return iter->current;
return ++iter->current;
}

/// Short helper function to actually interpret operators
long do_op(TokenType op, long a, long b) {
switch (op) {
case TOK_PLUS: return a + b;
case TOK_STAR: return a * b;
default: printf("Unsupported op type: %d\n", op); exit(EXIT_FAILURE);
}
}

/// Evaluate a line of input with only L-to-R and () precedence
long evaluate(TokenIter* tokens) {
Token* t;
long val_stack[MAX_TOKENS] = {0};
int sp = 0;
TokenType op_stack[MAX_TOKENS] = {0};
int op_sp = 0;
for (int i = 0; (t = token_next(tokens))->type != TOK_END; i++) {
switch (t->type) {
case TOK_NUM:
if (op_sp > 0) {
val_stack[sp - 1] = do_op(op_stack[--op_sp], t->val, val_stack[sp - 1]);
} else {
val_stack[sp++] = t->val;
}
break;
case TOK_PLUS: op_stack[op_sp++] = TOK_PLUS; break;
case TOK_STAR: op_stack[op_sp++] = TOK_STAR; break;
case TOK_OPEN_PAREN: {
long val = evaluate(tokens);
if (op_sp > 0) {
val_stack[sp - 1] = do_op(op_stack[--op_sp], val_stack[sp - 1], val);
} else {
val_stack[sp++] = val;
}
};
break;
case TOK_CLOSE_PAREN:
if (op_sp > 0) {
printf("End paren with unresolved operators.\n");
exit(EXIT_FAILURE);
}
if (sp > 1) {
printf("Unresolved integers on the stack.\n");
exit(EXIT_FAILURE);
}
return val_stack;
default: break;
}
}
if (op_sp > 0) {
printf("End paren with unresolved operators.\n");
exit(EXIT_FAILURE);
}
if (sp > 1) {
printf("Unresolved integers on the stack.\n");
exit(EXIT_FAILURE);
}
return val_stack;
}

/// Given only paren and L-to-R precedence, add up the result of
/// evaluating each line of input
long part1(const char* filename) {
int count;
TokenIter* lines = parse(filename, &count);

long total = 0;
for (int i = 0; i < count; i++) {
total += evaluate(&lines[i]);
free(lines[i].tokens);
}

free(lines);
}

/// Helper macro for unraveling the stack of operators.
/// Each operator pops two values off the value stack, operates on them
/// and disappears, pushing the result back on the value stack.
#define UNRAVEL_OPS \
while (op_sp != 0) { \
long a = val_stack[--sp]; \
long b = val_stack[--sp]; \
val_stack[sp++] = do_op(op_stack[--op_sp], a, b); \
}

/// Evaluate a line of input with addition taking precedence over
/// multiplication, and () being highest precedence
long evaluate_plus_prec(TokenIter* tokens) {
Token* t;
long val_stack[MAX_TOKENS] = {0};
int sp = 0;
TokenType op_stack[MAX_TOKENS] = {0};
int op_sp = 0;
for (int i = 0; (t = token_next(tokens))->type != TOK_END; i++) {
switch (t->type) {
case TOK_NUM: val_stack[sp++] = t->val; break;
case TOK_STAR:
UNRAVEL_OPS;
op_stack[op_sp++] = TOK_STAR;
break;
case TOK_PLUS: op_stack[op_sp++] = TOK_PLUS; break;
case TOK_OPEN_PAREN: val_stack[sp++] = evaluate_plus_prec(tokens); break;
case TOK_CLOSE_PAREN:
UNRAVEL_OPS;
if (sp > 1) {
printf("Unresolved integers on the stack.\n");
exit(EXIT_FAILURE);
}
return val_stack;
default: break;
}
}
UNRAVEL_OPS;
if (sp > 1) {
printf("Unresolved integers on the stack.\n");
exit(EXIT_FAILURE);
}
return val_stack;
}

#undef UNRAVEL_OPS

/// Add up the result of each line of input assuming precedence goes
/// () before + before *.
long part2(const char* filename) {
int count;
TokenIter* lines = parse(filename, &count);

long total = 0;
for (int i = 0; i < count; i++) {
total += evaluate_plus_prec(&lines[i]);
free(lines[i].tokens);
}

free(lines);