const normalPairs = [
    '()', '[]', '{}', // English parenthesis, brackets, braces
    '（）', '⎜⎟', '⁽⁾', '₍₎', '⎛⎞', '⎝⎠', '⦅⦆', '⸨⸩', '❪❫', '⸨⸩', '﴾﴿', '﹛﹜', '﹝﹞', '｟｠', // alternative parenthesis
    '⟨⟩', '⦑⦒', '⁅⁆', '〈〉', '❬❭', '❲❳', '❴❵', '⟦⟧', '⟨⟩', '⟪⟫', '⟬⟭', '⦇⦈', '⦉⦊', '⦋⦌', '⦍⦎', '⦏⦐', '⦑⦒', '⦗⦘',
    '❮❯', '⠦⠴', // quotation marks that is easier to handle
    '《》', '〈〉', '「」', '｢｣', '【】', '〔〕', '［］', '『』', '〖〗', '｛｝', // brackets and braces in CJK
    '⏜⏝', '︵︶', '﹃﹄', '﹁﹂', '︗︘', '︵︶', '︷︸', '︹︺', '︻︼', '︽︾', '︿﹀', '﹁﹂', '﹇﹈', // vertical symbols
    '❴❵', '❬❭', '❨❩', '❪❫', '❲❳', '❮❯', // ornament symbols
    '«»', '‹›', '༺༻', '༼༽', '᚜᚛',
]

export class PairCannotMatchError extends Error { }

export function balanceParenthesis(text: string) {
    const pairingMap = new Map<string, string>() // map the opening element to the closing element
    const reversePairingMap = new Map<string, string>()
    for (const pair of normalPairs) {
        pairingMap.set(pair[0], pair[1])
        reversePairingMap.set(pair[1], pair[0])
    }

    const stack: string[] = []
    for (let i = 0; i < text.length; i += 1) {
        const char = text[i]
        if (pairingMap.get(char) !== undefined) {
            stack.push(char)
        }
        if (reversePairingMap.get(char) !== undefined) {
            if (stack.pop() !== reversePairingMap.get(char)) {
                throw new PairCannotMatchError('WORLD IN CRISIS! I cannot balance your symbols!')
            }
        }
    }

    const returnChars: string[] = []

    for (let i = stack.length - 1; i >= 0; i -= 1) {
        const char = stack[i]
        returnChars.push(pairingMap.get(char)!)
    }

    return returnChars.join('')
}