Solving Facebook Hacker Cup "Balanced Smileys" with definite clause grammar and B-Prolog

Facebook Hacker Cup 2015 Qualification Round is running right now (January 8, 2015 at 4:00 PM PST – January 11, 2015 at 4:00 PM PST), and I want to give another example of a Hacker Cup problem that is very suitable for solving with tabled Prolog (in addition to Dynamic programming solution for Facebook Hacker Cup problem "AAAAAA" in B-Prolog).

Balanced Smileys problem from Facebook Hacker Cup 2013 Qualification Round asks to find if an input string with possible smileys in it has balanced parentheses.

An input string has balanced parentheses if it consists of one of the following (quoted from the problem statement):

- An empty string ""
- One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
- An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
- A message with balanced parentheses followed by another message with balanced parentheses.
- A smiley face ":)" or a frowny face ":("

The very first line of the input contains the number of test cases (input strings to check for balanced parentheses): this can be up to 50.

For a clever O(N) solution see the official editorial, and here is my solution which is almost a literal translation of the problem specification to B-Prolog, but is fast enough (BalancedSmileys.pl):

:- table_all.

symbol --> " " | ":" | [C], {C >= 0'a, C =< 0'z}.

balanced --> "" | symbol | ":)" | ":(" 
                | "(", balanced, ")" 
                | balanced, balanced.

do_case(Case_num, S) :-
    ( balanced(S, []) -> Result = "YES" ; Result = "NO" ),
    format("Case #~w: ~s\n", [Case_num, Result]).

main :-
    readLine(Tstr_), append(Tstr, [10], Tstr_), number_codes(T, Tstr),
    foreach(Case_num in 1..T, [S_, S], (
                readLine(S_),
                append(S, [10], S_), % strip nl (ASCII 10),
                do_case(Case_num, S)
           )).

The code uses definite clause grammar (DCG): symbol can be a space, a colon, or a low-case letter; balanced expression is an empty string, or a symbol, or a smiley face, or a frowny face, or a balanced expression inside parentheses, or two balanced expressions one after another.

The do_case predicate tries to parse an input string S as a balanced expression. If nothing left after parsing ([]), then the input string is balanced.

table_all declaration at the beginning of the program tells B-Prolog to table (memoize) all predicate calls. This is necessary because the grammar for balanced is left-recursive, and without tabling the program will loop and eat memory until no available memory left.

main looks somewhat complicated for a simple task of reading an integer and several strings and passing them to another predicate: I can't find a better way to read the data from the standard input. Maybe preprocessing with Python or sed to add a full stop after each input line is a better way – then in Prolog it would be just read(T) instead of readLine(Tstr_), append(Tstr, [10], Tstr_), number_codes(T, Tstr).

The current Hacker Cup qualification round lasts 3 days: there is plenty of time to experiment. So I encourage you to try to solve a problem or two with a tool which is different from what you use in your daily coding, and I think Prolog is a good candidate.