CODEWITHSUNDEEP
pythonalgorithm
Vishesh
Vishesh

Reputation: 289

Python program to check matching of simple parentheses

I came across this exercise of checking whether or not the simple brackets "(", ")" in a given string are matched evenly.

I have seen examples here using the stack command which I haven't encountered yet. So I attempted a different approach. Can anyone tell me where I am going wrong?

def matched(str):
    ope = []
    clo = []
    for i in range(0,len(str)):
        l = str[i]
        if l == "(":
            ope = ope + ["("]
        else:
            if l == ")":
                clo = clo  + [")"]
            else:
                return(ope, clo)
    if len(ope)==len(clo):
        return True
    else:
        return False

The idea is to pile up "(" and ")" into two separate lists and then compare the length of the lists. I also had another version where I had appended the lists ope and clo with the relevant I which held either ( or ) respectively.

Upvotes: 16

Views: 99210

Answers (30)

Kavitha Madhavaraj
Kavitha Madhavaraj

Reputation: 592

My solution here works for brackets, parentheses & braces

openList = ["[", "{", "("]
closeList = ["]", "}", ")"]


def balance(myStr):
    stack = []
    for i in myStr:
        if i in openList:
            stack.append(i)
        elif i in closeList:
            pos = closeList.index(i)
            if stack and (openList[pos] == stack[-1]):
                stack.pop()
            else:
                return "Unbalanced"
    if len(stack) == 0:
        return "Balanced"
    return "Unbalanced"


print(balance("{[()](){}}"))

Upvotes: 15

Nwawel A Iroume
Nwawel A Iroume

Reputation: 1379

for a balanced string, we can find an opening brace followed by it closing brace. if you do this basic check you could remove the checked substring and check the remaining string. At the end, if the string is not empty then it is not balanced.

def is_balanced(s: str) -> bool:
    while any([x in s for x in ["", "", ""]]):
        s=s.replace("{}", "").replace("[]","").replace("()","")
    return s==""

Upvotes: 0

Teivaz
Teivaz

Reputation: 5675

The problem with your approach is that you don't consider the order. Following line would pass: ))) (((. I'd suggest to keep the count of open and closed parenthesis:

  • counter starts from 0
  • every ( symbol increments counter
  • every ) symbol decrements counter
  • if at any moment counter is negative it is an error
  • if at the end of the line counter is 0 - string has matching parenthesis

Upvotes: 4

Shyam Gupta
Shyam Gupta

Reputation: 511

s='{[]{()}}}{'
t=list(s)
cntc=0
cnts=0
cntp=0
cntc=min(t.count("{"),t.count("}"))
cnts=min(t.count("["),t.count("]"))
cntp=min(t.count("("),t.count(")"))
print(cntc+cnts+cntp)

Upvotes: 0

Baxromov
Baxromov

Reputation: 43

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

def isValid(s):
    stack = []
    for i in s:
        if i in open_list:
            stack.append(i)
        elif i in close_list:
            pos = close_list.index(i)
            if open_list[pos] == stack[len(stack)-1]:
                stack.pop()
            else:
                return False
    if len(stack) == 0:
        return True
    else:
        return False

print(isValid("{[(){}]}"))

Upvotes: 0

Shoham
Shoham

Reputation: 7304

def matched(str):
    braces = {"{": "}", "(": ")", "[": "]"}
    stack = []
    for c in str:
        if c in braces.keys():
            stack.append(c)
        elif c in braces.values():
            if not stack:
                return False
            last_brace = stack.pop()
            if braces[last_brace] != c:
                return False
    if stack:
        return False
    return True

print(matched("()"))
>> True
print(matched("(}"))
>> False
print(matched("}{"))
>> False
print(matched("}"))
>> False
print(matched("{"))
>> False
print(matched("(ff{fgg} [gg]h)"))
>> True

Upvotes: 0

Muriithi Derrick
Muriithi Derrick

Reputation: 342

The best way to understand this snippet is to follow along with all kind of scenarios.

in_data = ['{','[','(']
out_data = ['}',']',')']

def check_match(statements):
    stack = []
    for ch in statements:
        if ch in in_data:
            stack.append(ch)
        if ch in out_data:
            last = None
            if stack: 
                last = stack.pop()
            if last is '{' and ch is '}':
                continue
            elif last is '[' and ch is ']':
                continue
            elif last is '(' and ch is ')':
                continue
            else:
                return False
    if len(stack) > 0:
        return False
    else:
        return True

print(check_match("{www[eee}ee)eee"))
print(check_match("(ee)(eee[eeew]www)"))
print(check_match("(ss(ss[{ss}]zs)zss)"))
print(check_match("([{[[]]}])"))

Upvotes: 0

jliu1999
jliu1999

Reputation: 12

just modified Henry Prickett-Morgan's code a little bit to handle it more sensibly, namely taking into account that the number of "(" matches that of ")" but string starts with ")" or ends with "(" which are apparently not right.


def ValidParenthesis(s):
    count = 0
    if s[0] == ')' or s[-1] == '(':
      return False
    else:
      for c in s:
        if c == '(':
          count += 1
        elif c == ')':
          count -= 1
        else:
          continue
      return count == 0

Upvotes: 0

Amit JS
Amit JS

Reputation: 133

A little different one.

expression = '{(){({)}}'
brackets = '[](){}'
stack  = []
balanced = False
for e in expression:
    if e in brackets and stack: # Popping from the stack if it is closing bracket
        if stack [-1] == brackets[brackets.index(e)-1]:
            stack.pop()
            balanced = True
            continue # it will go to the new iteration skipping the next if below
    if e in brackets: # Push to stack if new bracket in the expression
        stack .append(e)
        balanced = False
balanced = 'Balanced' if balanced and not stack  else 'Unbalanced'
print(balanced, stack)

Upvotes: 0

Brad Solomon
Brad Solomon

Reputation: 40918

An alternative to check for balanced nested parentheses:

def is_balanced(query: str) -> bool:
    # Alternative: re.sub(r"[^()]", "", query)
    query = "".join(i for i in query if i in {"(", ")"})
    while "()" in query:
        query = query.replace("()", "")
    return not query


for stmt in [
    "(()()()())",    # True
    "(((())))",      # True
    "(()((())()))",  # True
    "((((((())",     # False
    "()))",          # False
    "(()()))(()",    # False
    "foo",           # True
    "a or (b and (c or d)",  # False
    "a or (b and (c or d))"  # True
    "a or (b and (c or (d and e)))",  # True
]:
    print(stmt)
    print("Balanced:", is_balanced(stmt))
    print()

It works by:

  1. Removing everything but parentheses
  2. Recursively remove innermost parentheses pairs
  3. If you're left with anything besides the empty string, the statement is not balanced. Otherwise, it is.

Upvotes: 3

Alain T.
Alain T.

Reputation: 42133

You can do this in a couple of lines using accumulate (from itertools). The idea is to compute a cumulative parenthesis level going through the string with opening parentheses counting as level+1 and closing parentheses counting as level-1. If, at any point, the accumulated level falls below zero then there is an extra closing parenthesis. If the final level is not zero, then there is a missing closing parenthesis:

from itertools import accumulate
def matched(s):
    levels = list(accumulate((c=="(")-(c==")") for c in s))
    return all( level >= 0 for level in levels) and levels[-1] == 0

Upvotes: 2

Ajinkya Vadane
Ajinkya Vadane

Reputation: 21

parenthesis_String = input("Enter your parenthesis string")
parenthesis_List = []
for p in parenthesis_String:
    parenthesis_List.append(p)
print(parenthesis_List)

if len(parenthesis_List)%2 != 0:
    print("Not Balanced Wrong number of input")

for p1 in parenthesis_List:
    last_parenthesis = parenthesis_List.pop()
    print(last_parenthesis)
    if (p1 == '{' and last_parenthesis == '}' or p1 == '[' and last_parenthesis == ']' or p1 == '(' and last_parenthesis == ')'):
        print("Balanced")
    else:
        print("Not balanced")

Upvotes: 0

sub234
sub234

Reputation: 1

    #function to check if number of closing brackets is equal to the number of opening brackets
    #this function also checks if the closing bracket appears after the opening bracket
    def matched(str1):
        if str1.count(")")== str1.count("("):
            p1=str1.find("(")
            p2=str1.find(")")
            if p2 >= p1:
                str1=str1[p1+1:p2]+ str1[p2+1:]
                if str1.count(")")>0 and str1.count("(")>0:
                    matched(str1)
                return True
            else:
                return False
        else:
            return False

    matched(str1)

Upvotes: 0

photonic.bean
photonic.bean

Reputation: 344

Although I'm not proposing a fix to your implementation, I suggest a cleaner and more pythonic version of the @kreld solution:

def check_parentheses(expr):
    s = []
    for c in expr:
        if c in '(':
            s.append(c)
        elif c in ')':
            if not len(s):
                break
            else:
                s.pop()
    else:
        return not len(s)
    return False

# test -----------------------------------------------------------------
test_expr = [')(', '(()', '())', '(', ')', '((', '))', '(()())', '(())',
             '()', '()(())']
for i, t in enumerate(test_expr, 1):
    print '%i\t%s\t%s' % (i, t, check_parentheses(t))

# output ---------------------------------------------------------------
1       )(      False
2       (()     False
3       ())     False
4       (       False
5       )       False
6       ((      False
7       ))      False
8       (()())  True
9       (())    True
10      ()      True
11      ()(())  True

Upvotes: -1

Nitheesh MN
Nitheesh MN

Reputation: 628

this code works fine 

def matched(s):
  p_list=[]
  for i in range(0,len(s)):
    if s[i] =='(':
      p_list.append('(')
    elif s[i] ==')' :
      if not p_list:
        return False
      else:
        p_list.pop()
  if not p_list:
    return True
  else:
    return False

Upvotes: 3

Abhishek Kumar
Abhishek Kumar

Reputation: 1

you can check this code.
This code don't use stack operations. 

def matched(s):
  count = 0
  for i in s:
    if i is "(":
      count += 1
    elif i is ")":
      if count != 0:
        count -= 1
      else:
        return (False)

  if count == 0:
    return (True)
  else:
    return (False)

Upvotes: 0

JeffreyC
JeffreyC

Reputation: 640

here's another way to solve it by having a counter that tracks how many open parentheses that are difference at this very moment. this should take care all of the cases.

def matched(str):
    diffCounter = 0
    length = len(str)
    for i in range(length):
        if str[i] == '(':
            diffCounter += 1
        elif str[i] == ')':
            diffCounter -= 1
    if diffCounter == 0:
        return True
    else:
        return False

Upvotes: 1

Firdauz Fanani
Firdauz Fanani

Reputation: 19

foo1="()()())("  

def bracket(foo1):
    count = 0
    for i in foo1:
        if i == "(":
           count += 1
        else:
           if count==0 and i ==")":
               return False
           count -= 1

   if count == 0:
       return True
   else:
       return False

bracket(foo1)

Upvotes: -1

user6882757
user6882757

Reputation: 

def parenthesis_check(parenthesis):
    chars = []
    matches = {')':'(',']':'[','}':'{'}
    for i in parenthesis:
        if i in matches:
            if chars.pop() != matches[i]:
                return False
        else:
            chars.append(i)
    return chars == []

Upvotes: -1

whackamadoodle3000
whackamadoodle3000

Reputation: 6748

The simplest code ever!!

def checkpar(x):
    while len(''.join([e for e in x if e in "()"]).split('()'))>1: x=''.join(x.split('()'))
    return not x

Upvotes: 0

Belal Iqbal
Belal Iqbal

Reputation: 11

Simplest of all , though all of you guys have done good:

def wellbracketed(s):
    left=[]
    right=[]
    for i in range(0,len(s)):``
        if s[i]=='(':
            left=left+['(']
        elif s[i]==')':
            if len(left)!=0:
                right=right+[')']
        else:
            return False

    return(len(left)==len(right))

Upvotes: 1

Arjun P P
Arjun P P

Reputation: 39

if "(" ,")" these two characters are not present then we don't want to return true or false just return no matching found. if matching found i just checking the count of both characters are same then return true, else return false

def matched(str):
   count1=0
   count2=1
   for i in str:
       if i =="(":
           count1+=1:
       elif i==")":
           count2+=1:
       else:
           print "no matching found for (,)"
   if count1==count2:
        return True
   else:
        return False

Upvotes: 1

Ravil
Ravil

Reputation: 9

More advanced example in which you additionally need to check a matching of square brackets '[]' and braces '{}' pars. 

string = '([]{})'

def group_match(string):

    d = {
    ')':'(',
    ']':'[',
    '}':'{'
    }

    list_ = []

    for index, item in enumerate(string):
        if item in d.values():
            list_.append(item)

        elif (item in d.keys()) and (d.get(item) in list_):
            list_.pop()

    return len(list_) == 0

Upvotes: 0

Arshad Syed
Arshad Syed

Reputation: 1

input_str = "{[()](){}}"
strblance=""

for i in input_str:

    if not strblance:
        strblance = strblance+i
    elif (i is '}' and strblance[len(strblance)-1] is '{') \
        or ( i is']'and strblance[len(strblance)-1] is '[') \
        or ( i is ')'and strblance[len(strblance)-1] is '('):
            strblance = strblance[:len(strblance)-1]
    else:
        strblance = strblance+i

if not strblance:

    print ("balanced")

else:

    print ("Not balanced")

Upvotes: 0

Akshitha Shetty
Akshitha Shetty

Reputation: 19

In case u also need to find the position of the first mismatching bracket from left u can use the below code which also cover certain edge cases:

def isBalanced(expr):
    opening=set('([{')
    new=set(')]}{[(')
    match=set([ ('(',')'), ('[',']'), ('{','}') ])
    stack=[]
    stackcount=[]
    for i,char in enumerate(expr,1):
        if char not in new:
            continue
        elif char in opening:
            stack.append(char)
            stackcount.append(i)
        else:
            if len(stack)==0:
                print(i)
                return False
            lastOpen=stack.pop()
            lastindex=stackcount.pop()
            if (lastOpen, char) not in match:
                print (i)
                return False
    length=len(stack)
    if length!=0:
      elem=stackcount[0]
      print (elem)
    return length==0
string =input()
ans=isBalanced(string)
if ans==True:
    print("Success")

Upvotes: 1

Bruno Thomas
Bruno Thomas

Reputation: 1229

if the parenthesis sequence is not an issue (strings like )( ) this code is faster :

def matched_parenthesis(s):
    return s.count('(') == s.count(')')

Tested with 15KB string, it is ~20μs v.s. 1ms iterating over the whole string.

And for me the order is not an issue as the underlying protocol guaranties that the string is well-formed.

Upvotes: 1

Rajiv
Rajiv

Reputation: 412

a = "((a+b)*c)+(b*a))"

li = list(a)
result = []

for i in range(0, len(a)):

    if a[i] == "(":
        result.append(i)
    elif a[i] == ")":
        if len(result) > 0:
            result.pop()
        else:
            li.pop(i)

for i in range(0, len(result)):
    li.pop(result[i])

print("".join(li))

Upvotes: 3

kreld
kreld

Reputation: 752

This checks whether parentheses are properly matched, not just whether there is an equal number of opening and closing parentheses. We use a list as a stack and push onto it when we encounter opening parentheses and pop from it when we encounter closing parentheses.

The main problem with your solution is that it only counts the number of parentheses but does not match them. One way of keeping track of the current depth of nesting is by pushing opening parentheses onto a stack and popping them from the stack when we encounter a closing parenthesis.

def do_parentheses_match(input_string):
    s = []
    balanced = True
    index = 0
    while index < len(input_string) and balanced:
        token = input_string[index]
        if token == "(":
            s.append(token)
        elif token == ")":
            if len(s) == 0:
                balanced = False
            else:
                s.pop()

        index += 1

    return balanced and len(s) == 0

Upvotes: 15

Henry Prickett-Morgan
Henry Prickett-Morgan

Reputation: 564

A very slightly more elegant way to do this is below. It cleans up the for loop and replaces the lists with a simple counter variable. It also returns false if the counter drops below zero so that matched(")(") will return False.

def matched(str):
    count = 0
    for i in str:
        if i == "(":
            count += 1
        elif i == ")":
            count -= 1
        if count < 0:
            return False
    return count == 0

Upvotes: 19

Łukasz Rogalski
Łukasz Rogalski

Reputation: 23233

Most blatant error done by you is:

    if l == ")":
        clo = clo  + [")"]
    else:
        return(ope, clo)  # here

By using return, you exit from function when first char not equal to "(" or ")" is encountered. Also some indentation is off.

Minimal change which allows your code to run (although it won't give correct answers for all possible input strings) is:

def matched(str):
    ope = []
    clo = []
    for i in range(0,len(str)):
        l = str[i]
        if l == "(":
            ope = ope + ["("]
        elif l == ")":
            clo = clo  + [")"]
    if len(ope)==len(clo):
        return True
    else:
        return False

Upvotes: 6

Related Questions