I have some program, which produces strings of that kind:

s1 = '((q∧p)∧((q∨p)→s))'

or

s2 = (¬((r→s)∨q))

Furthermore I have the index position i1 of some '('-bracket or ')'-bracket.

I'm searching the index i2 position of the corresponding ')' or '('-bracket such that in the inner string between i1 and i2 (or i2 and i1) the count of '('-brackets is the same as the count of ')'-brackets.

Is their a simple function which represents that corresponding index?

CodePudding user response：

You could use stack and put pairs (index,char).

When you will try to put ) then you should start remove pairs until you get ( - this will be ( corresponding to this ). Because you have pairs index,char so you can check if one of them has expected index i1 or i2 and then you may get index from other pairs to have expected result

s1 = '((q∧p)∧((q∨p)→s))'

i1 = 1  # 5


stack = []

for index, char in enumerate(s1):
    if char == ')':
        while True:
            index2, char2 = stack.pop(-1)
            if char2 == '(':
                if index2 == i1 or index == i1:
                    print(index2, index, s1[index2:index 1])
                break
    else:
        stack.append( (index,char) )

Result:

1 5 (q∧p)

If you put code in function then you can run it for different values.

def match(text, i1):

    stack = []
    
    for index, char in enumerate(text):
        if char == ')':
            while True:
                index2, char2 = stack.pop(-1)
                if char2 == '(':
                    if index2 == i1 or index == i1:
                        print(f'i1: {i1:2} => {text[i1]} | result: {index2:2}, {index:2} => {text[index2:index 1]}')
                    break
        else:
            stack.append( (index,char) )

# ----

s1 = '((q∧p)∧((q∨p)→s))'

print('---', s1, '---')
for i1 in [0, 1, 5, 7, 8, 12, 15, 16]:
    match(s1, i1)

s2 = '(¬((r→s)∨q))'

print('---', s2, '---')
for i1 in [0, 2, 3, 7, 10, 11]:
    match(s2, i1)

Result:

--- ((q∧p)∧((q∨p)→s)) ---
i1:  0 => ( | result:  0, 16 => ((q∧p)∧((q∨p)→s))
i1:  1 => ( | result:  1,  5 => (q∧p)
i1:  5 => ) | result:  1,  5 => (q∧p)
i1:  7 => ( | result:  7, 15 => ((q∨p)→s)
i1:  8 => ( | result:  8, 12 => (q∨p)
i1: 12 => ) | result:  8, 12 => (q∨p)
i1: 15 => ) | result:  7, 15 => ((q∨p)→s)
i1: 16 => ) | result:  0, 16 => ((q∧p)∧((q∨p)→s))
--- (¬((r→s)∨q)) ---
i1:  0 => ( | result:  0, 11 => (¬((r→s)∨q))
i1:  2 => ( | result:  2, 10 => ((r→s)∨q)
i1:  3 => ( | result:  3,  7 => (r→s)
i1:  7 => ) | result:  3,  7 => (r→s)
i1: 10 => ) | result:  2, 10 => ((r→s)∨q)
i1: 11 => ) | result:  0, 11 => (¬((r→s)∨q))

EDIT:

Simpler code - it puts only index for ( from text (and skip other chars) and when it gets ) from text then it gets last index from stack to have indexes for corresponding chars ( and )

def match(text, idx):

    stack = []
    
    for index1, char in enumerate(text):
        if char == '(':
            # put every `(` on stack (or rather its index)
            stack.append( index1 )
        elif char == ')':
            # get `(` for current `)
            index2 = stack.pop(-1)
            if index1 == idx or index2 == idx:
                return index1, index2

# --- main ---

text = '((q∧p)∧((q∨p)→s))'

print('---', text, '---')

for idx in [0, 1, 5, 7, 8, 12, 15, 16]:
    result = match(text, idx)

    if result: # to detect `None`
        index1, index2 = result
        print(f'idx: {idx:2} => {text[idx]} | result: {index2:2}, {index1:2} => {text[index2:index1 1]}')
    else:
        print("can't find for idx:", idx)

# ---

text = '(¬((r→s)∨q))'

print('---', text, '---')

for idx in [0, 2, 3, 7, 10, 11]:
    result = match(text, idx)

    if result: # to detect `None`
        index1, index2 = result
        print(f'idx: {idx:2} => {text[idx]} | result: {index2:2}, {index1:2} => {text[index2:index1 1]}')
    else:
        print("can't find for idx:", idx)

Using range(len(text)) it can find all matching pairs ( )

text = '(¬((r→s)∨q)) ((q∧p)∧((q∨p)→s))'

print('---', text, '---')

for idx in range(len(text)):
    if text[idx] == '(':  # skip duplicated results for `)`
        result = match(text, idx)
        
        if result: # to detect `None`
            index1, index2 = result
            print(f'idx: {idx:2} => {text[idx]} | result: {index2:2}, {index1:2} => {text[index2:index1 1]}')
        #else:
        #    print("can't find for idx:", idx)

The same for enumerate(text)

print('---', text, '---')

for idx,char in enumerate(text):
    if char == '(':  # skip duplicated results for `)`
        result = match(text, idx)
        
        if result: # to detect `None`
            index1, index2 = result
            print(f'idx: {idx:2} => {text[idx]} | result: {index2:2}, {index1:2} => {text[index2:index1 1]}')
        #else:
        #    print("can't find for idx:", idx)

Result:

--- (¬((r→s)∨q)) ((q∧p)∧((q∨p)→s)) ---
idx:  0 => ( | result:  0, 11 => (¬((r→s)∨q))
idx:  2 => ( | result:  2, 10 => ((r→s)∨q)
idx:  3 => ( | result:  3,  7 => (r→s)
idx: 13 => ( | result: 13, 29 => ((q∧p)∧((q∨p)→s))
idx: 14 => ( | result: 14, 18 => (q∧p)
idx: 20 => ( | result: 20, 28 => ((q∨p)→s)
idx: 21 => ( | result: 21, 25 => (q∨p)