Parse a nested parentheses

Question

Objective

Mimic Haskell's reads :: ReadS ().

Or in other words, parse nested parentheses. Since the target type is () (the type with one possible value), "parsing" means discarding a leading nested parentheses.

Valid Input

"Nested parentheses" means (), (()), ((())), and so on. That is, leading nonzero (s and trailing )s of the same number.

But there's a twist. The parser must munch also leading or intercalated whitespaces. So for example, the following strings are valid to be munched:

• ( )
• ()
• ( () )

Note that trailing whitespaces are not to be munched.

Whitespaces

The following ASCII characters are always considered a whitespace:

• \t U+0009; Horizontal Tab
• \n U+000A; Line Feed
• \v U+000B; Vertical Tab
• \f U+000C; Form Feed
• \r U+000D; Carriage Return
• U+0020; Space

For each of the following Unicode characters, it is implementation-defined to consider it a whitespace:

• U+0085; Next Line
• U+00A0; No-Break Space
• U+1680; Ogham Space Mark
• U+2000; En Quad
• U+2001; Em Quad
• U+2002; En Space
• U+2003; Em Space
• U+2004; Three-Per-Em Space
• U+2005; Four-Per-Em Space
• U+2006; Six-Per-Em Space
• U+2007; Figure Space
• U+2008; Punctuation Space
• U+2009; Thin Space
• U+200A; Hair Space
• U+2028; Line Separator
• U+2029; Paragraph Separator
• U+202F; Narrow No-Break Space
• U+205F; Medium Mathematical Space
• U+3000; Ideographic Space

All other characters are never considered a whitespace.

Error

If the string doesn't start with a nested parentheses, the parser shall fall in an erroneous state. Ways that indicates an error include:

• Monadic failing
• Returning an erroneous value
• Raising/Throwing an error

Output

When the parser successfully munched a nested parentheses, the parser shall output the unmunched part of string.

Examples

Valid example

• When given (), the output is an empty string.
• When given ( ) Hello, the output is Hello. Note the leading whitespace of the output.
• when given ((())))), the output is )).

Erroneous example

• Empty string
• ((()
• (()())
• (H)
• Hello, world!

Ungolfed solution

C

Returns a null pointer for an error.

#include <stdbool.h>
#include <stdlib.h>

char *readMaybeUnit(char *str) {
    bool p = false;
    unsigned c = 0;
    while (*str != '\0') {
        switch (*str) {
        case '(':
            p = true;
            ++c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto parseRightParentheses;
        }
        ++str;
    }
    parseRightParentheses: while (*str != '\0') {
        switch (*str) {
        case ')':
            if (1 >= c) {
                if (1 == c)
                    ++str;
                c = 0;
                goto returnReadMaybeUnit;
            }
            --c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto returnReadMaybeUnit;
        }
        ++str;
    }
    returnReadMaybeUnit: return p && 0 == c ? str : NULL;
}

Answer 1

Retina 0.8.2, 32 31 bytes

^(\s*\()+(?<-1>\s*\))+(?(1)$.)

Try it online! Link includes test cases. Returns the original string on error. Considers the given control characters as white space, plus any Unicode characters (such as space) in the Separator group, plus U+0085. If only the minimal white space is desired, this can be achieved by prefixing e`. Explanation:

^(\s*\()+

Match some open parentheses at the start of the string.

(?<-1>\s*\))+

Match some close parentheses.

(?(1)$.)

Check that the same number of open and close parentheses were matched.

Delete the matched parentheses.

Alternative solution, also 31 bytes:

r`^(?<-1>\s*\()+(\s*\))+(.*)
$2

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:

r`

Start matching at the end of the string and work backwards (like a lookbehind would).

(.*)

Match as much result as possible.

(\s*\))+

Match some close parentheses.

^(?<-1>\s*\()+

Match the open parentheses at the start of the string. The number of close parentheses must be at least as many as the number of open parentheses for the balancing group to succeed, but it can't be more because the (.*) ensures that as few close parentheses are matched as possible.

$2

Keep everything except the matched parentheses.

Previous 32-byte solution that returns the empty string on error:

1!`(?<=^(?<-1>\s*\()+(\s*\))+).*

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:

1!`

Output the matched part of the first match.

(?<=^(?<-1>\s*\()+(\s*\))+)

Ensure that the match starts after balanced parentheses. Note that this is a lookbehind, so the match is processed right-to-left - the )s are matched first, then a ( can be matched for each ). There can't be too many )s because the lookbehind would have matched earlier, meaning that this is no longer the first match.

.*

Match the rest of the string. This actually counts as part of the match, and therefore becomes the resulting output.

Answer 2

Haskell, 83 76 bytes

c?(a:b)|elem a" \t\n\r\v\r"=c?b|a==c=[b]
_?_=[]
f x='('?x>>=(:)<*>f>>=(')'?)

Try it online!

Since this question to imitate Haskell's parsing I thought it would be nice to give this a try using Monadic parsing in Haskell. The result is actually really short. I use [] as my monad because it is just way shorter than Maybe or Either.

---

What is monadic parsing?

Put simply monadic parsing is a type of parsing in which a parser is a function from a string to some optional type of a the remaining string and some data

type Parser a = String -> Option (a, String)

Here our Option type is a list, and we are just validating rather than producing any data, so our parser looks like:

type Parser a = String -> [ String ]

Where our parser takes some string and returns all possible suffixes of valid parses. The empty string represents a failure to parse because no suffixes means that no valid parse was found.

This way of structuring things makes it super easy to combine parsers. For example if we have a parser p which parses the regex \s*( and a parser q which parses the regex \s*) then we can make a parser that parses the expression \s*(\s*) using the Kleisli arrow

(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)

Meaning the result is p >=> q. We can also do other combinators.

---

So here's how I use it in my answer.

The first thing we do is implement ?, which takes a character c returns a parser the regex \s*c (where c is the character). Essentially this consumes a prefix made of any amount of whitespace followed by a single character. This is only ever called on ( and ).

With this we implement f which is the parser that the challenge asks for. We don't actually have the Kleisli arrow in Prelude but I will write it as if we did for clarity and then show how we remove Kleisli arrows.

f = ('('?) >=> (:)<*>f >=> (')'?)

So we have three parsers first, it must start with some whitespace followed by a ( then some gobbledygook parser and then it must end with some whitespace followed by a ).

The gobbledygook (:)<*>f can be expressed more clearly as

\ x -> x : f x

Which is to say it is it matches everything the f parser does but also matches the empty string.

So our f parser matches:

Parentheses enclosing, either the empty string or another f.

Now to remove our Kleisli arrows we use >>= which has the similar type signature:

(>>=) :: m a -> (a -> m b) -> m b

So we take an argument from f, pass it to the first parser and change all of our (>=>)s to (>>=)s.

Answer 3

Python 2, 122 bytes

def f(s,c=0,p='('):a=s[:1];return[f(s[1:],c+"()".find(a)%-3+1,[p,a][a>p])if(a in(p,')'))|a.isspace()else 0,s][`c`+p=="0)"]

Returns 0 on error.

Try it online!

Python 3, 125 bytes

def f(s,c=0,p='('):a=s[:1];return[f(s[1:],c+"()".find(a)%-3+1,[p,a][a>p])if(a in(p,')'))|a.isspace()else 0,s][(c,p)==(0,')')]

Returns 0 on error.

Try it online!

---

Python 2 (non-recursive), 173 170 166 153 bytes

def p(s):c=i=a=0;t="""
while i<len(s):
 if~-s[i].isspace():
	if%r!=s[i]:break
	c+=%s
 i+=1""";exec t%('(','1')+t%(')',"-1\n\tif c==0:a=s[i+1:]");return a

Returns 0 on error.

Try it online!

We could save another 2 bytes if we returned the original string on error, but then inputs '()' and '' would give the same output ''.

• -4 bytes, thanks to @ovs !

Answer 4

Perl 5, (-p) 22 bytes

s/^(\s*\((?1)?\s*\))//

Try it online!

Using recursive regex. The shorter \s*\((?0)?\s*\) didn't work because of start anchor missing.

The error case is given by the result of substitution operation :

• 1 - success
• "" - failed