Question

Algorithm design：Suppose that three types of parentheses are allowed in an expression: parentheses, square brackets, and curly braces. Please design an efficient algorithm to determine whether the parentheses in the expression are correctly paired. Please write down the algorithm idea and steps.

Please explain what kind of data structure is used to solve the problem, and then give the specific algorithm steps

Answer 1

1) A stack will be used to solve the problem.

Algorithm steps:

Declare a stack S.
Now traverse the input string one character at a time.
If the character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack S.
If the character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack S.
If the popped character is the matching starting bracket then continue to next character, else parenthesis are not balanced - stop loop and return False.
After full traversal of the input string, if there is some starting bracket left in stack then return False as the string is not balanced.
Pseudocode:

function balancedbracket(inputString):
Stack S <- empty stack
for character in inputString:
if character == '(' or character == '{' or character == '[':
S.push(character)
else:
temp = S.pop()
if character == ')' and temp != '(':
return False
if character == ']' and temp != '[':
return False
if character == '}' and temp != '{':
return False
if S.empty():
return True
return False

THANK YOU!! PLEASE VOTE