## 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

Casper

My Haskell solution. It uses the shunting-yard algorithm to convert it to a postfix string and then evals the postfix string. Today's part 2 was obvious the moment I read part 1 so I went for this approach. So to solve part 2 I only had to change a `2` to a `3`. Took 24 seconds from submitting the answer to part 1 to submitting the answer to part 2.

``````import Data.Char
import Data.Bifunctor as Bf

precedence :: Char -> Int -- Change precedence level of + to 2 for part 1
precedence c = case c of '+' -> 3; '*' -> 2; '(' -> 1; ')' -> 1;

shouldPopStack :: Char -> Char -> Bool
shouldPopStack x top = precedence x <= precedence top && top /= '('

popWhile :: Char -> (String, String) -> (String, String)
popWhile c (out, []) = (out, [])
popWhile c (out, x:stack) =
if shouldPopStack c x then popWhile c (x:out, stack) else (out, x:stack)

shunting :: String -> (String, String) -> String
shunting [] (out, stack) = reverse stack ++ out
shunting ('(':xs) (out, stack) = shunting xs (out, '(':stack)
shunting (')':xs) (out, stack) =
let (ops, rest) = span (/= '(') stack
in shunting xs (reverse ops ++ out, tail rest)
shunting ('+':xs) yard = shunting xs (Bf.second ('+':) \$ popWhile '+' yard)
shunting ('*':xs) yard = shunting xs (Bf.second ('*':) \$ popWhile '*' yard)
shunting (x  :xs) (out, stack) = shunting xs (x:out, stack)

evalPostfix :: String -> (Int, String)
evalPostfix ('+':xs) =
let (left, rest)   = evalPostfix xs
in Bf.first (left+) \$ evalPostfix rest
evalPostfix ('*':xs) =
let (left, rest)  = evalPostfix xs
in Bf.first (left*) \$ evalPostfix rest
evalPostfix (x:xs) = (digitToInt x, xs)

main :: IO ()
main = do
input <- lines <\$> readFile "input.txt"
print \$ sum \$ map (\s -> fst \$ evalPostfix \$ shunting (filter (/= ' ') s) ([],[])) input
``````