TDD Kata 14 – Exclamation Mark Series

This is my weekly Kata post. Read the first one to learn what it is all about.

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 left and right to 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"

Source: https://www.codewars.com/kata/exclamation-marks-series-number-17-put-the-exclamation-marks-and-question-marks-to-the-balance-are-they-balanced

Leave a Reply

Your email address will not be published. Required fields are marked *