Interview Question: Check for balanced parentheses in an expression

Asked in : Amazon , Microsoft

Difficulty level: Medium

Problem Statement

We have to check if a string containing opening and the closing brackets is balanced or not. The string can contain ’(’, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’

A string is said to be balanced if it has as many opening brackets of a certain type as it has closing brackets of that type and if no bracket is unmatched.

Write a function which will take string as a parameter and return boolean if string is balanced. We will implement this using Swift 5.0

Example

input  : [][]()
output : true
input  : (([[}}}}}}
output : false

Solution

The problem points to a very interesting data structure called Stack. Since after encountering a closing bracket, we are checked the last processed value if the pair matches, then we are removing it. This problem can be solved very easily using stack. The Stack is LIFO (last in first out) data structure with only one entry and exit point.

Bonus tip: Swift arrays have build-in stack functions like popLast() and last which will be handy.

Approach

  1. We will iterate the input string and push in the stack if opening brackets are found.
  2. On encountering a closing bracket we will check:-
    1. If the stack is empty, return false. Since there are no opening brackets to match. (Example, input = “}]]”).
    2. We will compare the last stack element with the current character, if it is matching bracket case then we will pop the last element using popLast().
    3. Otherwise, we will return false.
  3. After exhausting the string ideally, our stack should be empty. If this is non-empty then return false.
  4. We will maintain a dictionary to create a mapping for possible matching brackets. Since matching cases are only three, this will help to write clean code and avoid multiple conditions joined using OR.

Lets code </>

  1. Initialize the stack and dictionary mapping. I have also created a string containing opening brackets which i will use to identify opening bracket case using contains().

2. Iterating over string and check case for opening brackets using

3. Check closing brackets case using last variable on Array and find suitable match using the dictionary. Pop() the stack if they match.

Final Code

Complexity:

Time :- O(n) // For iterating over the string

Space : O(n) // for stack space.

You can check out the full code with test suites on github.

Hope you liked this post, please share it with your peers preparing for interviews. Happy Coding!!

Leave a Reply

Your email address will not be published. Required fields are marked *