Check for `balanced parentheses`

in the expression

## Scope

This article tells how to check balanced parentheses using stack.

In this article we will learn implementation in different programming language.

In this article we will learn time complexity of the stack approach.

## Takeaways

`Balanced parentheses`

means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.

## Problem Statement

Given an input expression string of length `n`

consisting of three types of parentheses – `{,}`

,`(,)`

,`[,]`

.Check for balanced parentheses in the expression (well-formedness) using Stack. Parentheses are balanced if:

- The same kind of parentheses are used to close any open ones.
- The proper sequence must be used to close any open parentheses.

## Example

- Input: expression = ~
`([]){}[[(){}]{}]`

Output: Yes, Balanced - Input: expression =
`[(]))`

Output: No, Not Balanced - It’s real life application is during the compilation of any code

## Example Explanation

- As in
**example 1**, there is every closing bracket according to their corresponding opening brackets so yes this is balanced parentheses. - In the second
**example**, it is observable that the parentheses are not balanced because the`(`

at the 2nd position in the expression should be closed before the closing of the`]`

. - In the 3rd example, there is no
`{`

for the`}`

that is in line number`8`

of the code. Due to this, an error will be raised if we will try to run the code.

## Constraints

- $1<=n<=10^3$
- All of characters in the sequence ∈
`(,)`

,`{,}`

,`[,]`

.

## Approach

We must make an observation in order to resolve this problem. The most recent opening parenthesis must coincide with the subsequent closing symbol as you read symbols from left to right. Additionally, it’s possible that the very last symbol processed will be the one to match the first opening symbol. Opening and closing symbols are matched from the inside out, in the opposite order from which they first appear. This is a hint that the issue can be resolved using stacks.

### Algorithm

- Declare an empty stack.
- Now start traversing the input string.
- If you come across an opening bracket while traversing the string, add it to the stack.
- Else the current character is a closing bracket. In this case, check to see if the top element of the stack is of the corresponding opening type and if it is then pop the top element from the stack and if not, then return false.
- If the stack is empty after traversing the string, return true; otherwise, return false.

### Code Implementation

**In C++**

*// CPP program for balancing the paranthesis*
bool is_BalancedParentheses(string str) {
int x = str.size(); *// storing size of input expression*
stack<char> opening_Brackets;
*// iterating over the full expression using for loop*
for (int k = 0; k < x; k++)
{
*// if opening bracket encounters then directly push it into stack.*
if (str[k] == '{' || str[k] == '(' || str[k] == '[') {
opening_Brackets.push(str[k]);
}
else {
*// If stack is empty return false*
if (opening_Brackets.empty()) {
return false;
}
*// If ) is encountered then check if top of the stack have ( or not *
if (str[k] == ')') {
char last = opening_Brackets.top();
opening_Brackets.pop();
if (last != '(') {
return false;
}
}
*// If } is encountered then check if top of the stack have { or not *
if (str[k] == '}') {
char last = opening_Brackets.top();
opening_Brackets.pop();
if (last != '{') {
return false;
}
}
*// If ] is encountered then check if top of the stack have [ or not*
if (str[k] == ']') {
char last = opening_Brackets.top();
opening_Brackets.pop();
if (last != '[') {
return false;
}
}
}
}
return opening_Brackets.empty();
}

**In Java**

*// Java program for balancing the paranthesis*
class Solution {
boolean is_BalancedParentheses(String str) {
int x = str.length(); *// storing size of input expression*
Stack<Character> opening_Brackets = new Stack<>();
*// iterating over the full expression using for loop*
for (int k = 0; k < n; k++) {
*// if opening bracket encounters then directly push it into stack.*
if (str.charAt(k) == '{' || str.charAt(k) == '(' || str.charAt(k) == '[') {
opening_Brackets.push(str.charAt(k));
}
else {
*// If stack is empty return false*
if (opening_Brackets.empty()) {
return false;
}
*// If ) is encountered then check if top of the stack have ( or not *
if (str.charAt(k) == ')') {
char last = opening_Brackets.peek();
opening_Brackets.pop();
if (last != '(') {
return false;
}
}
*// If } is encountered then check if top of the stack have { or not *
if (str.charAt(k) == '}') {
char last = opening_Brackets.peek();
opening_Brackets.pop();
if (last != '{') {
return false;
}
}
*// If ] is encountered then check if top of the stack have [ or not *
if (str.charAt(k) == ']') {
char last = opening_Brackets.peek();
opening_Brackets.pop();
if (last != '[') {
return false;
}
}
}
}
return opening_Brackets.isEmpty();
}
}

**In Python**

*# Python program for balancing the paranthesis*
def is_BracketsBalanced(exp):
st = [] *# creating empty stack*
for ch in exp:
if ch in ["{", "(", "["]:
st.append(ch)
else:
*# If stack is empty return false*
if not st:
return False
curr_char = st.pop()
*# If current char is { and top of the stack is not } then return false *
if curr_ch == '{':
if ch != "}":
return False
*# If current char is ( and top of the stack is not ) then return false *
if curr_ch == '(':
if ch != ")":
return False
*# If current char is [ and top of the stack is not ] then return false *
if curr_ch == '[':
if ch != "]":
return False
*# if any bracket still there in stack then return false*
if st:
return False
return True
if __name__ == "__main__":
exp = "{()}[]"
if is_BracketsBalanced(exp):
print("Yes, Balanced")
else:
print("NO, Not Balanced")

### Output

```
Yes, Balanced
```

### Time Complexity:

As we are traversing over the expression of length n only once using the for loop so O(n) will be it’s time complexity.

### Space Complexity:

As we are creating a new stack and the size of stack can grow upto the size of the input string which is n, so O(n) auxiliary space will be used.

## Conclusion

- One can solve this balanced parentheses problem using stack.
- There is some sort of nested symbol in almost every type of notation that needs to match in a balanced order.
- O(n) time complexity and O(n) auxiliary space is consumed in this stack approach.