Balanced Paranthesis

Given a string expression, check if brackets present in the expression are balanced or not. Brackets are balanced if the bracket which opens last, closes first.

You need to return true if it is balanced, false otherwise.

Note: This problem was asked in initial rounds in Facebook

Note:- I try to solve this problem using Linked List, python Queue, and List

Sample Input 1 :

{ a + [ b+ (c + d)] + (e + f) }

Sample Output 1 :

true

Sample Input 2 :

{ a + [ b - c } ]

Sample Output 2 :

false

	"Implementation of stack using linked list "
	class Node:
	def __init__(self,data):
	self.data=data
	self.next=None
	class LinkedList:
	def __init__(self):
	self.head=None
	self.size=0
	def PushLL(self,arr):
	NewNode=Node(arr)
	NewNode.next=self.head
	self.head=NewNode
	self.size=self.size+1
	def PopLL(self):
	self.head=self.head.next
	self.size=self.size-1
	def BalancedParanthesis(str):
	ll=LinkedList()
	for i in str:
	if i in "{[(":
	ll.PushLL(i)
	if i is ")":
	if ll.size==0 or ll.head.data!="(":
	return False
	ll.PopLL()
	if i is "}":
	if ll.size==0 or ll.head.data!="{":
	return False
	ll.PopLL()
	if i is i is "]":
	if ll.size==0 or ll.head.data!="[":
	return False
	ll.PopLL()
	if ll.size==0:
	return True
	return False
	ele=input()
	if BalancedParanthesis(ele):
	print("true")
	else:
	print("false")

view raw Balanced Paranthesis Using Linked List.py hosted with ❤ by GitHub

	"Implementation of stack using list "
	arr=[]
	def BalancedParanthesis(str):
	for i in str:
	if i in "{[(":
	arr.append(i)
	if i is ")":
	if len(arr)<1 or arr[-1]!="(":
	return False
	arr.pop()
	if i is "}":
	if len(arr)<1 or arr[-1]!="{":
	return False
	arr.pop()
	if i is i is "]":
	if len(arr)<1 or arr[-1]!="[":
	return False
	arr.pop()
	if len(arr)==0:
	return True
	return False
	str = input()
	if BalancedParanthesis(str):
	print("true")
	else:
	print("false")

view raw Balanced Paranthesis Using List.py hosted with ❤ by GitHub

	"Implementation of stack using builtin queue "
	import queue
	q=queue.LifoQueue()
	def isBalanced(str):
	for i in str:
	if i is "[" or i is "{" or i is "(":
	q.put(i)
	if i is "]":
	if q.empty() or q.queue[-1]!="[":
	return False
	q.get()
	if i is ")":
	if q.empty() or q.queue[-1]!="(":
	return False
	q.get()
	if i is i is "}":
	if q.empty() or q.queue[-1]!="{":
	return False
	q.get()
	if q.empty():
	return True
	return False
	expression=input()
	if isBalanced(expression):
	print("true")
	else:
	print("false")

view raw Balanced Paranthesis Using Queue.py hosted with ❤ by GitHub