Bracket Monoid
(monoid/bracket.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/bracket.hpp"

Overview

A monoid for processing bracket sequences (parentheses matching). It maintains the number of successfully matched pairs, as well as the count of unmatched closing ) and opening ( brackets.

A sequence is considered a “valid bracket sequence” if both unmatched_right and unmatched_left are 0.

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/bracket.hpp"
#include <iostream>
#include <string>
#include <vector>

using BracketM = m1une::monoid::Bracket;

int main() {
    std::string S = "())(()()";
    int N = S.size();

    std::vector<BracketM::value_type> init_data(N);
    for (int i = 0; i < N; ++i) {
        init_data[i] = BracketM::make(S[i]);
    }

    m1une::ds::Segtree<BracketM> seg(init_data);

    // Query range [3, 8) -> "(()()"
    auto res = seg.prod(3, 8);

    std::cout << "Matched Pairs: " << res.matched << "\n"; // Output: 2
    std::cout << "Unmatched '(': " << res.unmatched_left << "\n"; // Output: 1
    std::cout << "Unmatched ')': " << res.unmatched_right << "\n"; // Output: 0

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_BRACKET_HPP
#define M1UNE_MONOID_BRACKET_HPP 1

#include <algorithm>

namespace m1une {
namespace monoid {

struct BracketNode {
    int matched;
    int unmatched_right;  // Count of unmatched ')'
    int unmatched_left;   // Count of unmatched '('
};

// Monoid for matching parentheses (Bracket Sequences).
struct Bracket {
    using value_type = BracketNode;
    static constexpr bool commutative = false;

    // The identity element is an empty sequence.
    static constexpr value_type id() {
        return {0, 0, 0};
    }

    // Merges two bracket sequences.
    // The unmatched '(' from the left perfectly matches the unmatched ')' from the right.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        int match = std::min(a.unmatched_left, b.unmatched_right);
        return {a.matched + b.matched + match, a.unmatched_right + b.unmatched_right - match,
                a.unmatched_left + b.unmatched_left - match};
    }

    // Helper to securely create a leaf node from a single character.
    static constexpr value_type make(char c) {
        if (c == '(') return {0, 0, 1};
        if (c == ')') return {0, 1, 0};
        return {0, 0, 0};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_BRACKET_HPP

#line 1 "monoid/bracket.hpp"



#include <algorithm>

namespace m1une {
namespace monoid {

struct BracketNode {
    int matched;
    int unmatched_right;  // Count of unmatched ')'
    int unmatched_left;   // Count of unmatched '('
};

// Monoid for matching parentheses (Bracket Sequences).
struct Bracket {
    using value_type = BracketNode;
    static constexpr bool commutative = false;

    // The identity element is an empty sequence.
    static constexpr value_type id() {
        return {0, 0, 0};
    }

    // Merges two bracket sequences.
    // The unmatched '(' from the left perfectly matches the unmatched ')' from the right.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        int match = std::min(a.unmatched_left, b.unmatched_right);
        return {a.matched + b.matched + match, a.unmatched_right + b.unmatched_right - match,
                a.unmatched_left + b.unmatched_left - match};
    }

    // Helper to securely create a leaf node from a single character.
    static constexpr value_type make(char c) {
        if (c == '(') return {0, 0, 1};
        if (c == ')') return {0, 1, 0};
        return {0, 0, 0};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page