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

• Below is the detailed algorithm for finding whether the given expression has balanced parentheses or not.
• Algorithm:

Function checkParentheses(expression):

1. Declare a stack of characters

2. Now start traversing the expression character by character

3 if current character is a opening one i.e, ( or { or [ then,

4. push it into stack

5. else if current character is a closing one i.e, ) or } or ] then,

6. pop the top character from stack

7. and check if the popped opening bracket matches current closing one

8. if matches then continue

9. else return false i.e, unbalanced parentheses

10. After the matching if we did not get to the result then

11. check if stack is empty then return true

12. otherwise return false

• The above algorithm computes if the expression has balanced parantheses or not by using a stack data structure which has the property of LIFO i.e, Last In First Out. So we traverse the expression from start and if we encounter an opening bracket of any of the three i.e, ( or { or [ then we add it to stack and when we encounter a closing bracket i.e, ) or } or ] then we check if the recent opening bracket was of the same type or not(as we have used stack we will get the recently added opening bracket in the top of it), if they are of the same type then we pop the opening one from stack and move forward traversing the expression otherwise we return false from the function as here the parentheses are unbalanced.
• In the end after traversing the expression if we did not find any unbalanced pair we check for stack to be empty or not, so if stack is empty then we return true otherwise if it contains some opening bracket then we return false as those brackets do not have their closing ones.
• The above algorithm runs in linear time as we inly use a loop(for/while) to traverse the expression and inside it to pop an element from stack i.e, an O(1) operation and all other comparisons made inside the loop are also constant time operation. So resultingly we have our algorithm to run in linear time i.e, in worst case , O(n) where n is the length of the expression.
• So what we used is a stack data structure to solve the problem.

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.