Regular expressions, as implemented by common programming languages, are way more powerful than "regular expressions", as intended by computer science theorists in connection with finite state automata. There are very good reasons behind this power. Even something very basic, such as backreferences, are beyond the capabilities of regular expressions. I found this: http://dev.perl.org/perl6/doc/design/apo/A05.html, where Larry Wall says: "... generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions".

-- Kushal Kumaran - 2011-09-19

Thanks for the pointer Kushal, I see there are dramatic changes/fixes to regexes coming with Perl 6.

-- Peter Thoeny - 2011-09-19

That tagging is a great idea. I've used recursion in some toy code of mine, which works well, but has less than wonderful performance, and it has the limitation that the inner parentheses must be processed away or the outer parentheses cannot be evaluated. I haven't tested this yet, but it does have potential.

That having been said, it looks to me like it'd be better to put the tag after the parentheses. That way, the parenthesis itself indicates the next character will be the first character of a tag. There's no way any non-parenthesis will be confused as a tag temporarily, triggering a back track. You then need to have a sequence to end the tag, but since you can't possibly be looking at a false positive, a single, non-digit character will do.

So, instead of

$ROUND-esc-1( $TIME-esc-2( -esc-2), $TIMEDIFF-esc-2( $TIME-esc-3(
  $T-esc-4( R$ROW-esc-5( -esc-5):C$COLUMN-esc-5( -1 -esc-5) -esc-4)
 -esc-3), day -esc-2) -esc-1)

you have

$ROUND(1. $TIME(2. )2., $TIMEDIFF(2. $TIME(3.
  $T(4. R$ROW(5. )5.:C$COLUMN(5. -1 )5. )4.
 )3., day )2. )1.

-- Ed Grimm - 2011-09-19

Thanks Ed for your insights. Not sure how much performance you gain by swapping the parenthesis with the escape token. The -esc- was just for visuals, in reality it is a null character. Does it make a difference in performance if you scan for .N( vs (N.? Your approach is better in a sense that you can take any non-digit char to terminate the sequence, vs. a null character to start the sequence.

-- Peter Thoeny - 2011-09-20

See Stackoverflow answer using this approach to change nested |x+2| to abs(x+2): https://stackoverflow.com/questions/66557385/regex-javascript-convert-strings-with-absolute-values-x-to-absx

JavaScript code:

function fixAbs(str) {
  const startTag = '{{s%L%}}';
  const endTag   = '{{e%L%}}';
  const absRegex = /\{\{s(\d+)\}\}(.*?)\{\{e\1\}\}/g;
  let level = 0;
  str = str
  .replace(/ /g, '')  // remove all spaces
  .replace(/(\|*)?(\w+)(\|*)?/g, function(m, c1, c2, c3) {
    // regex matches variables with all leading and trailing `|`s
    let s = c2;
    if(c1) {
      // add a start tag to each leading `|`: `{{s0}}`, `{{s1}}`, ...
      // and post-increase level
      s = '';
      for(let i = 0; i < c1.length; i++) {
        s += startTag.replace(/%L%/, level++);
      }
      s += c2;
    }
    if(c3) {
      // decrease level,
      // and add a end tag to each trailing `|`: `{{e2}}`, `{{e1}}`, ...
      for(let i = 0; i < c3.length; i++) {
        s += endTag.replace(/%L%/, --level);
      }
    }
    return s;
  });
  // find matching start and end tag from left to right,
  // repeat for each level
  while(str.match(absRegex)) {
    str = str.replace(absRegex, function(m, c1, c2, c3) {
      return 'abs(' + c2 + ')';
    });
  }
  // clean up tags in case of unbalanced input
  str = str.replace(/\{\{[se]-?\d+\}\}/g, '|'); 
  return str;
}

const testCases = [
  '|x|+12',
  '|x|+|y+|z||',
  '|x|+||y|+z|',
  '|x|+|x+|y|+z|',
  '|x|+|x+|y+|t||+z|',
  '|x|+12+|2+x|',
  '|x|+12+|x+2|'
].forEach(str => {
  let result = fixAbs(str);
  console.log('"' + str + '" ==> "' + result + '"');
});

Output:

"|x|+12" ==> "abs(x)+12"
"|x|+|y+|z||" ==> "abs(x)+abs(y+abs(z))"
"|x|+||y|+z|" ==> "abs(x)+abs(abs(y)+z)"
"|x|+|x+|y|+z|" ==> "abs(x)+abs(x+abs(y)+z)"
"|x|+|x+|y+|t||+z|" ==> "abs(x)+abs(x+abs(y+abs(t))+z)"
"|x|+12+|2+x|" ==> "abs(x)+12+abs(2+x)"
"|x|+12+|x+2|" ==> "abs(x)+12+abs(x+2)"

-- Peter Thoeny - 2021-03-10