| Safe Haskell | None |
|---|
Day18
Description
General - We kinda need to solve two problems here: We need to parse the expressions and we need to evaluate the expressions.
Looking at the expressions you can see an (binary) abstract syntax tree (AST) where every node is an expression. The (two) children are either a value or an expression again.
To build the AST we first convert the expression string from infix notation to postfix notation (RPN) (with the shunting-yard algorithm (SYA)).
Building the AST from RPN is trivial (Note: We make this easy by reversing the RPN (12+ -> +21)).
To evaluate the AST we just have to (recursively) walk the tree.
Part 1 - Evaluate all expressions and sum up the results.
Part 2 - Now we need to implement precedence (by peeking into the operators stack).
Synopsis
- data Expression
- = Add Expression Expression
- | Mul Expression Expression
- | Val Int
- | Nil
- input :: String -> [String]
- toPostfix :: String -> String
- toPostfixToken :: String -> String -> String -> String
- toPostfixToken' :: String -> String -> (String, String)
- toExpression :: String -> Expression
- reverse' :: String -> String
- eval :: Expression -> Int
- part1 :: [String] -> Int
- toPostfix2 :: String -> String
- toPostfixToken2 :: String -> String -> String -> String
- part2 :: [String] -> Int
Documentation
data Expression #
All possible expressions.
Constructors
| Add Expression Expression | |
| Mul Expression Expression | |
| Val Int | |
| Nil |
Instances
| Eq Expression # | |
Defined in Day18 | |
| Show Expression # | |
Defined in Day18 Methods showsPrec :: Int -> Expression -> ShowS show :: Expression -> String showList :: [Expression] -> ShowS | |
toPostfix :: String -> String #
Convert infix string into postfix (RPN) string (by running the shunting-yard algorithm (SYA)).
toPostfixToken :: String -> String -> String -> String #
Implement SYA (with no prededence; eval left to right)
toPostfixToken' :: String -> String -> (String, String) #
Implement SYA.
toExpression :: String -> Expression #
Turn a postfix/RPN string into an expression AST.
reverse' :: String -> String #
Reverse a/the give expression string (to make the operators asscociate to the left). Note: For this to work we need to flip the parenthis.
eval :: Expression -> Int #
(Recursively) Evaluate an expression.
toPostfix2 :: String -> String #
Same as above, but for part2.
toPostfixToken2 :: String -> String -> String -> String #
Same as above, but for part2 (implementing the precedence of + over *).