"开括号位置"

Question

我试图使一个函数传递一个字符串，它将是一个数学表达式和一个括号位置，返回我作为参数传递的位置的左括号的位置。在

示例：

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

应该返回0，因为包围位置4的括号在位置0处打开。在

我甚至试过了，但它只适用于一些表达式，取决于位置和我通过。在

我试过了

^{pr2}$

Answer 1

假设表达式始终有效，则问题很容易解决。在

• 初始化堆栈
• 穿过绳子
• 如果current char是左括号，则将其位置推到 堆栈
• 如果current char是右括号，则从 堆栈
• 如果到达所需的位置并且堆栈为空，则返回-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 2

你的代码似乎运行得很好，实际上，你只需要考虑没有匹配的左括号的情况，否则它将抛出一个异常。在

作为您的算法的一个小变化，我建议向后扫描表达式，计算您仍然需要的左括号的数量，并在该数字达到零时立即返回索引。在

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。在

注意，这个可以表示表达式中有不平衡的括号，但也可以完全正常，就像我上一个例子中一样。要检查括号是否不平衡，可以使用类似的算法，扫描整个字符串并检查计数是否平衡。在

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"