获取以“(”开头或以“)”结尾的子命题 (stringrepresentation) 的最后一个或第一个索引

Question

我有一些程序可以生成那种字符串：

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

或

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

此外，我有一些 '('-bracket 或 ')'-bracket 的索引位置 i1。

我正在搜索相应 ')' 或 '('-括号的索引 i2 位置，这样在 i1 和 i2（或 i2 和 i1）之间的内部字符串中，'('-括号的计数是与')'-括号的数量相同。

它们是表示相应索引的简单函数吗？

Answer 1

您可以使用 stack 并放置对 (index,char).

当您尝试放置 ) 时，您应该开始删除对，直到您得到 ( - 这将是 ( 对应于此 )。因为你有对 index,char 所以你可以检查其中一个是否有预期的索引 i1 或 i2 然后你可以从其他对中获得索引以获得预期的结果

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) )

结果：

1 5 (q∧p)

如果您将代码放在函数中，那么您可以运行它用于不同的值。

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)

结果：

--- ((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))

编辑：

更简单的代码 - 它仅从 text 中为 ( 放置索引（并跳过其他字符），当它从 text 中获取 ) 时，它获取最后一个 index 从 stack 获得相应字符 ( 和 )

的索引

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)

使用range(len(text))它可以找到所有匹配对( )

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)

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)

结果：

--- (¬((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)

获取以“(”开头或以“)”结尾的子命题 (stringrepresentation) 的最后一个或第一个索引

Get last or first index of subproposition (stringrepresentation) starting with '(' or ending with ')'

python

string

brackets