-1

I am trying to count the number of brackets in an input math expression. if there are not right brackets than left brackets, program should prompt users to tell them an error: 

"Unexpected right parenthesis between _ and _"

for example: 

expression = ( ( 1 + 2 ) ) ) )
output: Unexpected right parenthesis between ( ( 1 + 2 ) ) and ) )

Question: how do I get to the index between ( ( 1 + 2 ) ) and ) ) to print out my desired output?

Below is the code that I have now. I appreciate anyone who can help me with this. Thank you. 

tokenList = []
countLeft = 0
countRight = 0
mark1 = []
mark2 = []

expression = input("Enter an expression: ")
for i in expression.split(" "):
    tokenList.append(i)

for i in range(len(tokenList)): 
    if tokenList[i] == '(':
        countLeft += 1

    if tokenList[i] == ')':
        countRight += 1

if countLeft < countRight:
    for i in range(len(tokenList)):
        if tokenList[i] == '(': # this is to store the index  of '('
            mark1.append(i)

    for i in range(len(tokenList)):
        if tokenList[i] == ')': # this is to store the index of ')'
            mark2.append(i)

while (' and ')' in tokenList:
    tokenList.pop(mark1[-1])
    mark1.pop(-1)
    mark2.pop(0)

print("Unexpected right parenthesis between _ and _") 
if countRight < countLeft:
    print(f"There is {countLeft - countRight} unclosed left parenthesis in {expression}")
Jing Yi
  • 203
  • 4
  • 15

2 Answers2

2

You can iterate through the string and find the first point where the brackets become unmatched. One way to do this is just to add 1 to some total if you find a ( and subtract 1 if you find a ). If this number ever goes < 0 then you have a mismatch (and if it is > 0 at the end of the string). So something like

def find_mismatched_brackets(expression):
    out = "Unexpected right parenthesis between {} and {}"
    stack = 0
    for i, j in enumerate(expression):
        stack += 1 if j == '(' else -1 if j == ')' else 0
        if stack < 0:
            return out.format(expression[:i], expression[i:])

find_mismatched_brackets('( ( 1 + 2 ) ) ) )')

will print

'Unexpected right parenthesis between ( ( 1 + 2 ) )  and ) )'
tomjn
  • 5,100
  • 1
  • 9
  • 24
  • `stack += 1 if j == '(' else -1 if j == ')' else 0` is such an awkward expression, but actually reads very nicely. – Mad Physicist Aug 29 '19 at 11:42
  • @MadPhysicist yeah I debated with myself whether to include it :) One alternative would be to define a dictionary outside the loop such as `valid_chars = {'(': 1, ')': -1}` and then replace the `stack += ...` line with `stack += valid_chars.get(j, 0)` – tomjn Aug 29 '19 at 11:45
  • thank you so much all!! – Jing Yi Aug 29 '19 at 14:35
1

This is a perfect candidate for stacks. If you loop over all the characters in the string and every time you encounter a "(" you push it to your stack and every time you find a ")" you pop a "(" from your stack.

In the end you will end up with an empty stack, if everything is correct. Or you find a closing bracket when your stack is empty. That is when you know you have an unbalanced expression.

Something like this:

expr = "(( a + b ))))"
stack = []

for idx, char in enumerate(expr):
  if(char == '('):
    stack.append(char)

  if(char == ')'):
    if(len(stack) == 0):
      print('Unexpected right parenthesis between {0} and {1} '.format(expr[:idx], expr[idx:]))
      break
    else:
      stack.pop()
Floxx
  • 31
  • 5