[jibal]

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced.

If you have multiple kinds of brackets then you need the same number of counters. Each counter corresponds to the number of openers of that type currently on the stack. EDIT: this is wrong. Counters can't distinguish between [() and ([)

If you're writing a parser and you want to report the location of an unclosed opening bracket then you need the actual stack.

[vidarh]

You need the actual stack, I think, in the case of multiple types of openers without additional constraints, because if you just have raw counters you'd get tripped up by ([)] or similar.

So to generalise your point you need a counter for each transition to a different type of opener.

So (([])) needs only 2 counters, not 3.

You could constrain it further if certain types of openers are only valid in certain cases so you could exclude certain types of transitions.

EDIT:

([)] could indeed be handled by just additionally tracking the current open type. (([]]) is a better example, as it shows that to handle deeper nesting you need additional pieces of data that will grow at some rate (at most by the number of opens, possibly lower depending on which types can validly appear within which types)

[agumonkey]

maybe there's an encoding that can allow counting different ordered accumulations succintly.. (thinking out loud here)

ps: apparently there's already a lot of research on multidimensional dyck languages (somehow mentionned below)

https://arxiv.org/pdf/2307.16522

https://omelkonian.github.io/data/publications/d3.pdf

[spyrja]

FWIW it's a fairly straightforward algorithm. In C++:

  bool balanced(const string& text, const string& open, const string& close) {
    size_t length = text.size(), brackets = open.size();
    assert(close.size() == brackets);
    stack<char> buffer;
    for (size_t index = 0; index < length; ++index) {
      char ch = text[index];
      for (size_t slot = 0; slot < brackets; ++slot) {
        if (ch == open[slot])
          buffer.push(ch);
        else if (ch == close[slot]) {
          if (buffer.empty() || buffer.top() != open[slot])
            return false;
          buffer.pop();
        }
      }
    }
    return buffer.empty();
  }

[gpderetta]

Wouldn't two counters report "([)]" as being properly balanced?

[jibal]

No, there's an open [ when the ) is encountered. The problem is the other way around -- my algorithm would report [() as an error. Oops, back to the drawing board. Clearly no counting can tell the difference between [() and ([).