Check Balanced Parentheses in an Expression

Write a java code to check balanced parentheses in an expression using stack.

Given an expression containing characters ‘{‘,’}’,'(‘,’)’,'[‘,’]’. We have to write a code to check whether an input string has valid parentheses.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example –

i) {[]}) – Invalid

ii) {()}[] – Valid

For solving this kind of problem the choice of data structure is very important. Think for a moment which data structure should we choose to solve this problem?

Also, at the end of this tutorial i have shared a video tutorial link.

Programming Video Tutorials

Valid Parentheses String

Algorithm to check Balanced Brackets

In this tutorial, i am using  stack data structure to solve this problem efficiently. Here are the following steps to solve this problem.

i) First, we need to traverse an input string and pick each character at a time.

ii) If the current character is starting bracket ‘{‘, ‘(‘, ‘[‘ then push it in a stack.

iii) If the current character is closing bracket ‘}’, ‘)’, ‘]’ and the top of the stack is starting bracket then pop from the stack.

iv) After complete traversal, if the stack is empty then it is balanced parentheses otherwise it is not balanced.

Java Program to Reverse a String using Stack

Find Next Greater Element in an Array

Check Balanced Parentheses in an Expression using Stack – Java Code

We have discussed the algorithm to solve this problem. Let’s write a java code to implement this algorithm using stack data structure.

The time complexity of this approach is O(n) and it’s space complexity is also O(n).

Find the minimum element in a stack in O(1)

Find maximum element in a stack in O(1)

Sort a stack using recursion

Valid Parentheses LeetCode Solution

Balanced parentheses video tutorial