Position of opening parenthesis

Question

I'm trying to make a function that passed a string that would be a mathematical expression and a parenthesis position, return the position of the opening parenthesis of the position that I passed as a parameter.

example:

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

should return 0 because the parentheses that enclose position 4 open at position 0.

I even tried to do, but it only works with some expressions depending on the position and I pass.

I've tried

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

Your code seems to work quite well, actually, you just have to consider the case where there is no matching opening parentheses, otherwise it will throw an exception.

As a slight variation of your algorithm, I'd suggest scanning the expression backwards, counting the number of opening parenthesis you still need, and returning the index as soon as that number reaches zero.

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

For '(7*(1+4)-3)+1' and positions 2, 4, 9, and 11, this returns 0, 3, 0, and None, i.e. if no opening parenthesis is found (or not enough to match closing parentheses) it will return None.

Note that this could mean that there are unbalanced parentheses in the expression, but it could also be perfectly okay, as in my last example. To check for unbalanced parentheses, you could use a similar algorithm, scanning the entire string and checking whether the count is balanced.

Answer 2

This requires parsing only up to the position you provided. It does not attempt to enforce valid expressions. You should do that separately.

Something you didn't specify is for positions that are outside of any parentheses. I implemented it to return -1 for any positions that are not contained in parentheses.

Copy-Paste Code

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)

Output

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 3

Your problem is easy to solve assuming the expression is always valid.

• initialize a stack
• traverse the string
• if current char is an opening parenthesis, push its position to the stack
• if current char is a closing parenthesis, pop one element from the stack
• if you reach the wanted position and the stack is empty return -1
• else return the last element

Here's an implementation of the following:

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 4

This script assumes your expr string is parenthesis-balanced.

Explanation:

1. if expr[par] is not a closing parenthesis, the input is wrong (you have to specify the closing parenthesis as in your example).
2. note i return strings on error. this algorithm is just illustrative. return what you want, or raise exceptions.
3. the algorithm pushes every position of '(' it finds, and pops when finds a matching ')'. if the current position of the current ')' if the one you want, the popped '(' will be in the position you want, because the push and pop control parenthesis-balancing.

Code:

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"