The absolute value of a number \$x\$ is normally written as \$|x|\$. The left and right side of the absolute value uses the same symbol, so it is not immediately obvious how to parse nested absolute values e.g. \$||1-2|+|3-|4-5|||\$

Your goal is to parse such an expression containing nested absolute values:

The expression will be given as a string of characters.
For simplicity the expression will only contain single-digit numbers (or letters if that is easier in your language), the operators + and - (you can use any two distinct characters to represent these operations), and the symbol | for the left and right side of an absolute value.
You do not need to handle the case where a number is directly adjacent to an absolute value (e.g. 2|3| or |2|3)

Your output should be the same expression in a form that allows you to determine how the absolute values are bracketed.

The output has to satisfy the following rules:

  • The expression within an absolute value must not end with an operator ( + or - )
  • The expression within an absolute value cannot be empty
  • Each | has to be part of exactly one absolute value

You may assume there is a valid way to parse the given input.


|2|                ->  (2)
|2|+|3|            ->  (2)+(3)
||2||              ->  ((2))
||2|-|3||          ->  ((2)-(3))
|-|-2+3||          ->  (-(-2+3))
|-|-2+3|+|4|-5|    ->  (-(-2+3)+(4)-5)
|-|-2+|-3|+4|-5|   ->  (-(-2+(-3)+4)-5)
||1-2|+|3-|4-5|||  ->  ((1-2)+(3-(4-5)))

This is the shortest solution wins.

Optional additional requirement:

Also support expressions that allow a number direct before or after a bracket. If the result is not unique, you may return any valid solution.

test-cases (for optional requirement):

|2|3|4|  -> (2(3)4)
|2|3|4|  -> (2)3(4)
||3|4|   -> ((3)4)
|2|3-|4| -> (2)3-(4)
|1+|2|3| -> (1+(2)3)
|1+2|3|| -> (1+2(3))
  • \$\begingroup\$ The expression within a absolute value must not end with an operator. Do you have a testcase in mind where this could be a problem? I have a solution which doesn't check for this, but I'm having a hard time finding an example where this is actually an issue \$\endgroup\$
    – ovs
    Dec 5, 2023 at 14:10
  • 2
    \$\begingroup\$ @ovs one possible example would be parsing the second test case as (2(+)3) \$\endgroup\$
    – bsoelch
    Dec 5, 2023 at 14:13
  • \$\begingroup\$ Would |1+2|3|| be a valid test case for the optional requirement? \$\endgroup\$
    – Neil
    Dec 5, 2023 at 17:23
  • \$\begingroup\$ (Your optional requirement test cases seem to test for a number after a bracket, not before.) \$\endgroup\$
    – Neil
    Dec 6, 2023 at 0:46

7 Answers 7


JavaScript (ES6), 52 bytes


Try it online!


At each iteration, we look for the first substring consisting of:

  • \| a leading pipe
  • .*? the shortest possible string
  • [\d)] either a digit or a closing parenthesis
  • \| a trailing pipe

and replace the pipes with ( and ) respectively.

If a replacement occurs, the new string is less than the original string in lexicographical order, because the leading pipe is turned into an opening parenthesis. Hence the test s > (s = s.replace(...)) which triggers a recursive call if true.

NB: A safer way would be to use [^|]* instead of .*?. If you find a test case where .*? fails, please let me know.

  • \$\begingroup\$ The pattern works wonderfully with JavaScript regexes, but cannot make it work the same way with RE2, possibly because of differences in empty string matching. \$\endgroup\$ Dec 5, 2023 at 14:22
  • 1
    \$\begingroup\$ [^|]* wouldn't need a ?, would it? \$\endgroup\$
    – Neil
    Dec 5, 2023 at 15:09

Retina 0.8.2, 22 16 bytes


Try it online! Link includes test cases. Explanation:


Replace all |s that appear after digits with )s.


Replace the remaining |s with (s.

  • \$\begingroup\$ I think you can split this up into two separate replace to save a byte: TIO \$\endgroup\$
    – ovs
    Dec 5, 2023 at 14:42
  • \$\begingroup\$ @ovs I took your idea to its logical conclusion... \$\endgroup\$
    – Neil
    Dec 5, 2023 at 14:58

K (ngn/k), 27 22 bytes

Based on Arnauld's answer, but without regex.


Try it online!

Any closing parenthesis in the output directly follows a digit or another closing parenthesis, and none of the opening ones do. This means we can replace all consecutive |'s following a digit by closing parentheses. The remaining |'s are replaced by opening ones.

K (ngn/k), 36 bytes

My first idea, tests all ways of replacing | with parentheses using try/eval.


Try it online!

It is not very easy to show this is correct, as (1+) is a valid expression in K. However after toying around with this for quite some time, I'm convinced that you can't construct a valid input where this actually becomes a problem


Charcoal, 16 bytes


Try it online! Link is to verbose version of code. Explanation:


Loop over the input characters.


If the current characters is a | then output a ) or ( depending on whether the last non-| was less than 0.


Otherwise output the character and save it as the last non-|.


JavaScript (Node.js), 44 bytes


Try it online!

Look last non-pipe character before each pipe. Converting pipe to ) only when last non-pipe is a digit, and converting to ( otherwise. Does not work with the optional additional requirement.


05AB1E, 13 bytes


Port of @Neil's Charcoal answer, so make sure to upvote that answer as well!

Outputs as a list of characters.

Try it online or verify all test cases.


ε           # Map over the characters of the (implicit) input:
 '|Qi      '#  If the current character is a "|":
     žu     #   Push builtin string "()<>[]{}"
       ®    #   Push variable `®` (which is -1 by default)
        d   #   Check whether it's a non-negative (>=0) number
         è  #   Use that check (0 or 1) to (0-based) index into string "()<>[]{}"
    ë       #  Else:
     y      #   Simply push the current character
      ©     #   And store it in variable `®` (without popping)
            # (after which the mapped list of characters is output implicitly as result)

Haskell + hgl, 26 bytes


This solution uses a "regex" to replace each of the |s with either ( or ).

A closing paren must be preceded by a valid statement, and valid statements can only end in either digits, or a closing paren. Meanwhile a open paren can never come after a digit or a closing paren, so this classification is complete.

We translate these rules to the "regex":

(                  )+  -- at least once
 /d                    -- a digit
   (     )+            -- at least one of
    /|                 -- a |
      {)_              -- replaced with )
           |           -- or
            /|         -- a |
              {(_      -- replaced with (
                 |     -- or 
                  .    -- any character

Without "regex", 36 bytes


This is the same idea as the algorithm above, but implemented using parser combinators.

This is considerably longer, as parser combinators tend to be at a disadvantage to the "regex" when it comes to challenges involving the specific behavior of specific characters.

36 bytes


This is another solution which is also the same length, but which uses a mix of parser and non-parser functions.


Although these solutions don't exactly feel good, there is remarkably little I see in the way of improvement.


There's very little that can be done to improve the "regex" based solution. I have no plans to change the syntax of "regex" in the near future, and to be honest I don't even know what I would do.

  • The only thing I can think of is to make a combined version of gkx and gkY. This would pull the (...)+ out and save 3 bytes.


I have more thoughts here, but even with all my suggestions this doesn't come close to catching up with the regex.

  • The time has probably come for a combined version of <> and sO.
  • hh"|"")" is annoyingly long. There are two ways to solve this:
    • Simplest is that like other characters we could just add a shortcut to hh"|". Of course next time we are going to want to do something like hh"@""*" and this will have been completely useless, but if we keep adding these eventually we will get there.
    • A more principled solution would be to implement something like xx but taking a single string argument and unconsing it to get two arguments. e.g. xxh(x:xs)=xx x xs. This would allow it to be xxh"|)" which saves only a byte.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.