14
\$\begingroup\$

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.

Examples:

|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))
\$\endgroup\$
4
  • \$\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
  • 1
    \$\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

6 Answers 6

9
\$\begingroup\$

JavaScript (ES6), 52 bytes

f=s=>s>(s=s.replace(/\|(.*?[\d)])\|/,"($1)"))?f(s):s

Try it online!

Method

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.

\$\endgroup\$
2
  • \$\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
7
\$\begingroup\$

Retina 0.8.2, 22 16 bytes

T`|`)`\d\|+
\|
(

Try it online! Link includes test cases. Explanation:

T`|`)`\d\|+

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

\|
(

Replace the remaining |s with (s.

\$\endgroup\$
2
  • \$\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
5
\$\begingroup\$

K (ngn/k), 27 22 bytes

Based on Arnauld's answer, but without regex.

{`c$(84-0=\"0|"'x)!'x}

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.

{c@*<.[.:;;`]','c:+`c$(83+!2&x)!''x}

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

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 16 bytes

FS≡ι|§)(‹ψ0«ι≔ιψ

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

FS≡ι

Loop over the input characters.

|§)(‹ψ0

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-|.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 44 bytes

s=>s.replace(d=/./g,c=>c>{}?++d?')':'(':d=c)

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.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 13 bytes

ε'|Qižu®dèëy©

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.

Explanation:

ε           # 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)
\$\endgroup\$

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.