开括号的位置

Question

我正在尝试写一个函数，这个函数接收一个字符串，内容是一个数学表达式，还有一个括号的位置，然后返回这个位置对应的开括号的位置。

举个例子：

myfunction('(7 * 3) +1', 4)

这个函数应该返回 0，因为在位置4的括号是从位置0开始的。

我甚至尝试过这样做，但它只对某些表达式有效，具体取决于我传入的位置。

我尝试过：

def pos_open_parent(exp, pos_closed):

        temp_exp = exp[:pos_closed]
        count_open = 0
        count_closed = 1

        i = len(temp_exp) -1
        while count_open != count_closed:
                if temp_exp[i] == '(':
                        count_open += 1
                elif temp_exp[i] == ')':
                        count_closed += 1
                i -= 1
        return i + 1

Answer 1

这段话的意思是，只需要解析到你提供的位置。它不会检查表达式是否有效。你需要单独去做这个检查。

你没有提到的一点是，对于那些不在任何括号里的位置，我实现的方式是，如果位置不在括号内，就返回 -1。

复制粘贴代码

def myfunction(expression, position):
    open_positions = list()
    for i, c in enumerate(expression):
        if c == '(':
            # found a new open parens. everything after this points to here
            # until a new one is opened or this one is closed
            open_positions.append(i)
        if i == position:
            # this is the position we are looking for
            # return the current open parentheses position (or -1 if no parens)
            try:
                return open_positions[-1]
            except IndexError:
                return -1
        if c == ')':
            # closed a set of parentheses so nothing else can be inside
            # remove the current open parentheses
            open_positions.pop()  # finished parens before getting to position

expression          = '(1*((2+3)*4))+5'
visual_confirmation = '012345678901234'
for i in range(len(expression)):
    open_position = myfunction(expression, i)
    print 'open parens for position {} at {}'.format(i, open_position)

输出

open parens for position 0 at 0
open parens for position 1 at 0
open parens for position 2 at 0
open parens for position 3 at 3
open parens for position 4 at 4
open parens for position 5 at 4
open parens for position 6 at 4
open parens for position 7 at 4
open parens for position 8 at 4
open parens for position 9 at 3
open parens for position 10 at 3
open parens for position 11 at 3
open parens for position 12 at 0
open parens for position 13 at -1
open parens for position 14 at -1

Answer 2

你的问题很简单，只要这个表达式总是有效的。

• 先准备一个栈
• 遍历这个字符串
• 如果当前字符是一个左括号，就把它的位置放入栈里
• 如果当前字符是一个右括号，就从栈里弹出一个元素
• 如果你到达了想要的位置，而栈是空的，就返回 -1
• 否则返回栈里的最后一个元素

下面是这个过程的实现：

def yourfunction(first_arg, second_arg):
    stack = []
    for i, c in enumerate(first_arg):
        if i == second_arg:
            return -1 if len(stack) == 0 else stack.pop()
        if c == '(':
            stack.append(i)
        elif c == ')':
            if len(stack) > 0:  
                stack.pop()
            else:
                raise ValueError('Mathematical expression is invalid. Check your parenthesis')

print yourfunction('(7*3)+1', 4)
0
print yourfunction('((7)*3)+1', 6)
0
print yourfunction('((7)*(3)+1', 7)
5

Answer 3

这个脚本假设你的表达式字符串是括号配对好的。

解释：

1. 如果 expr[par] 不是一个闭合括号，那输入就是错误的（你必须像例子中那样指定闭合括号）。
2. 注意我在出错时返回字符串。这个算法只是个示例。你可以返回你想要的内容，或者抛出异常。
3. 这个算法会把每个找到的 '(' 的位置记录下来，当找到匹配的 ')' 时就把它弹出。如果当前的 ')' 是你想要的那个位置，那么弹出的 '(' 就会在你想要的位置，因为推入和弹出操作控制了括号的配对。

代码：

def find_matching_openin_par(expr, par):
    if expr[par] != ')':
        return "the specified pos is not a closing paren."
    else:
        opens = []
        for index, ch_ in enumerate(expr):
            if ch_ == '(':
                opens.append(index)
                #add a new opening paren. to the list
            elif ch_ == ')':
                #get the last added position of a "(" parenthesis.
                pos = opens.pop() #it may throw an exception if the string is unbalanced!
                if index == par:
                    #we keep that position, since all previously matched parenthesis were popped.
                    return pos
        return "not found. malformed string"

Answer 4

你的代码看起来运行得不错，不过你需要考虑一种情况，就是没有找到匹配的左括号，否则会出现错误。

我建议你稍微改进一下算法，可以试着从后往前扫描表达式，计算一下你还需要多少个左括号，然后一旦这个数字变成零，就返回当前的位置。

def pos_open_parens(exp, pos):
    count = 1                           # one open parens to find
    for i in range(pos, -1, -1):
        if exp[i] == ')': count += 1    # now we need one more...
        if exp[i] == '(': count -= 1    # found one!
        if count == 0: return i         # found all the parens we need
    return None                         # no matching open parens -> None

以 '(7*(1+4)-3)+1' 为例，当你检查位置 2、4、9 和 11 时，结果分别是 0、3、0 和 None。也就是说，如果没有找到左括号（或者左括号不够来匹配右括号），就会返回 None。

需要注意的是，这 可能 表示表达式中的括号不平衡，但也可能是完全正常的，就像我最后的例子那样。要检查括号是否平衡，你可以使用类似的算法，扫描整个字符串，看看括号的数量是否匹配。