Last week: Boolean Expression Engine
To the Kata description
Scroll down to this weeks Kata description
I was determined to build a real compiler for exercise, knowing that it would be a bit over the top for this particular challenge. The first step was a lexer that converts an input string to a list of tokens.
So
(x&y)|z
became
Token::openingBracket(),
Token::variable('x'),
Token::and(),
Token::variable('y'),
Token::closingBracket(),
Token::or(),
Token::variable('z')
At this point it’s pure syntax checking without context, so “)(&&&1” would be tokenized without errors, so I could implement it with a backtracking algorithm. Using TDD worked well here.
The next step was a parser that takes the list of tokens and converts them to an abstract syntax tree (AST) – this basically checks if the input is a valid program. It took me way longer than expected, but I (re)learned a few things about parsers and it was an interesting challenge.
I managed to create an LL(1) parsable grammar, which means that the next token read from the input determines which production rule was applied. Epsilon (ε) stands for “empty”.
EXPR => ( EXPR ) FUNC EXPR => ! EXPR FUNC EXPR => VALUE FUNC FUNC => ε FUNC => OP EXPR OP => & OP => | VALUE => 1 VALUE => 0 VALUE => VAR
I could not do this entirely test driven, since I was implementing the algorithm by the book, but I could use tests to verify the resuliting AST and find bugs in the implementation. Also I implemented the grammar definition with its rule lookup table separately from the actual parser, this again was a part where TDD worked for me.
At the end of the week it was more complex than expected and I still had not solved the Kata. There was still a big step missing, from the AST to actually running the program, i.e. evaluating the boolean expression with variables. I evaluated some ideas but did not have enough time to finish it, so it remained an incomplete result.
Throw everything away to start over
But I didn’t want to end the week without a success, so I tried out a completely different approach, more suitable for the problem: replacing simple expressions like “1&1” using regular expressions until there is nothing left to replace. I gave myself 30 minutes to see how it works, and… it worked!
This is the whole function:
function evaluate(string $expression) : bool
{
$expression = preg_replace('{\s}', '', $expression);
$replacements = [
'{\(([^()]+)\)}' => function($matches) {
return evaluate($matches[1]) ? '1' : '0';
},
'{!([01])}' => function($matches) {
return $matches[1] ? '0' : '1';
},
'{([01])&([01])}' => function($matches) {
return $matches[1] && $matches[2] ? '1' : '0';
},
'{([01])\|([01])}' => function($matches) {
return $matches[1] || $matches[2] ? '1' : '0';
},
];
do {
$replaced = 0;
foreach ($replacements as $pattern => $callback) {
$expression = preg_replace_callback($pattern, $callback, $expression, -1, $count);
$replaced += $count;
}
} while ($replaced > 0);
return (bool)$expression;
}
I didn’t add variables within the time frame but this would be just one more replacement upfront.
Fourteenth Kata: Exclamation Mark Series
After the last two Katas were quite heavy, let’s go for something small and quick this week. It’s a challenge from codewars.com, which is a nice platform to do Katas online in multiple languages, with some gamification on top.
Description
- Each exclamation mark weight is 2; Each question mark weight is 3. Put two string
leftandrightto the balance, Are they balanced?If the left side is more heavy, return
"Left"; If the right side is more heavy, return"Right"; If they are balanced, return"Balance".Examples
balance("!!","??") === "Right" balance("!??","?!!") === "Left" balance("!?!!","?!?") === "Left" balance("!!???!????","??!!?!!!!!!!") === "Balance"
