Question 4: Write a logic to verify the given input string is correctly balanced
Example:
Input: "[{()}]"
Output: Balanced
Input: "{(}([)])"
Output: Not Balanced
Input: "({()})"
Output: Balanced
Example:
Input: "[{()}]"
Output: Balanced
Input: "{(}([)])"
Output: Not Balanced
Input: "({()})"
Output: Balanced
Input: "[{(){[( )]}}]"
Output: Balanced
exp_data = {"{": "}", "[": "]", "(": ")", "<": ">"}
ReplyDeleteinput_exp = "<{}>([])[]"
open_element = list()
if len(input_exp)%2 == 0:
for s in input_exp:
if s in exp_data.keys():
open_element.append(s)
else:
curr_close = exp_data.get(open_element[-1])
if s == curr_close:
open_element.pop()
else:
print('not balanced')
break
else:
print('equally balanced')
else:
print('not balanced')
Thankz Ravi, really a good algorithm,
DeleteSimplified your code a little.
exp_data = {"{": "}", "[": "]", "(": ")", "<": ">"}
# input_exp = list("{[{([<>])}]}")
input_exp = list("{[]{(<>)[]()}}")
exp_open_data = list()
print("input expression :" + str(input_exp))
if len(input_exp) % 2 == 0:
for item in input_exp:
if item in exp_data.keys():
exp_open_data.append(item)
elif item == exp_data.get(exp_open_data[-1]):
exp_open_data.pop()
else:
print(f"Given expression {input_exp} is not equally balanced")
break
else:
print(f"Given expression {input_exp} is equally balanced")
else:
print(f"Given expression {input_exp} is not equally balanced")
This logic fails when the input starts with closed one of any brackets. like "][(){}"
ReplyDeleteit throws index out of bound exception.
Need to revisit this logic.
did a small change in elif inside for loop "elif len(exp_open_data) > 0 and item == exp_data.get(exp_open_data[-1]):"
Deleteexp_data = {"{": "}", "[": "]", "(": ")", "<": ">"}
# input_exp = list("{[{([<>])}]}")
input_exp = list("{[]{(<>)[]()}}")
exp_open_data = list()
print("input expression :" + str(input_exp))
if len(input_exp) % 2 == 0:
for item in input_exp:
if item in exp_data.keys():
exp_open_data.append(item)
elif len(exp_open_data) > 0 and item == exp_data.get(exp_open_data[-1]):
exp_open_data.pop()
else:
print(f"Given expression {input_exp} is not equally balanced")
break
else:
print(f"Given expression {input_exp} is equally balanced")
else:
print(f"Given expression {input_exp} is not equally balanced")