## Problem Statement

A string expression of parenthesis with the letters `"(", ")", "{", "}", "[", "]"`

is supplied to you.

The expression is called **balanced** with respect to the parenthesis if

the same type of closing brackets `)", "}", "]"`

is used to close open brackets `"(", "{", "["`

.

The correct **sequence** in which they appear must be followed when closing open brackets.

Verify whether or not the supplied statement is balanced.

## Example

Consider the expression string `{[()]}`

here as we can see there are three **nested parenthesis** and each opening parenthesis has a corresponding closing parenthesis. Hence the output from our parenthesis checker must be giving **a valid parenthesis expression**.

Consider another expression string `{{{[(()`

here as we can see there are multiple opening parenthesis but only one parenthesis has a corresponding closing parenthesis. Hence the output from our parenthesis checker should say **an invalid parenthesis expression**.

## Example Explanation

Let us consider the case of input expression string `{[()]}`

.

The expression contains six characters: `{`

, `[`

, `(`

, `)`

, `]`

, `}`

.

**Traversing** the string from the first character we see that for the first character `{`

the corresponding closing parenthesis is on the sixth character `}`

, for the second character `[`

the corresponding closing parenthesis is on the fifth character `]`

, and for the third character `(`

the corresponding closing parenthesis is on the fourth character `)`

.

Thus we observe that for each opening parenthesis there is a corresponding closing parenthesis present, moreover, the closing parentheses are in the exact same sequence as that of the opening parenthesis. Thus the string satisfies the requirements of a **valid parenthesis expression**.

If the given string had more characters like the sequence of `({[`

opening parenthesis without any closing parenthesis then the expression would have been termed as ***not valid parenthesis expression**.

## Input/Output

**Sample A**

Input string: `"{}[](){}{([{()}])}"`

Output: `expression is balanced`

**Sample B**

Input string: `"{}[]("`

Output: `expression is not balanced`

## Constraints

The **constraints** can be put on the input expression, those being:

- The input must be a string only.
- The input expression must consist of parenthesis only
`()[]{}`

. - The input expression cannot be an empty string (as that is always a valid parenthesis expression).
- The input string should be of limited ($10^4$ characters max) length.

## Algorithm 1 – Using Stack

In this approach, the **parenthesis checker** is implemented using a `stack`

data structure.

### Algorithm

The algorithm has the following steps:

- We
**traverse**the string starting from the first character to the last sequentially. For each character:- Any open symbol, such as
`(`

,`{`

or`[`

that is encountered, is placed onto the**stack** - Any one of the below cases is executed if an end symbol (i.e.,
`)`

,`}`

,`]`

) is encountered.- If the close symbol that was encountered while traversing matches its corresponding open symbol, the open symbol that is at the
**Top Of the Stack**(TOS) is popped out.

(OR) - The
**TOS**(Top Of Stack) is verified, and if the close symbol encountered does not match the open symbol,`False`

is returned since no matching symbol was found. Thus, the**string is not a valid parenthesis expression**.

(OR) - If the stack is empty, the
**TOS**(Top Of Stack) is checked, and if it is,`False`

is returned since there isn’t an open symbol in the stack. Thus the**string is not a valid parenthesis expression**.

- If the close symbol that was encountered while traversing matches its corresponding open symbol, the open symbol that is at the

- Any open symbol, such as
- If the string traversal is complete.
- If the stack is empty, it means the
**string is a valid parenthesis expression**, and`True`

is returned. - If the stack is not empty, it means some open parentheses are not closed. Hence the
**string is not a valid parenthesis expression**and`False`

is returned.

- If the stack is empty, it means the

### Code Implementation

**Python**

```
def parenthesis_checker(parenthesis_expression):
stack = []
parenthesis_pairs = { '(': ')',
'{': '}',
'[': ']' }
# traversing the string expression
for parenthesis in parenthesis_expression:
if parenthesis in ["(", "{", "["]:
# push the closing parenthesis in the stack
stack.append(parenthesis_pairs[parenthesis])
# If current character is not opening
# parenthesis, then it is a closing one.
# and the stack cannot be empty at this point.
elif not stack:
return False
elif parenthesis != stack.pop():
return False
# see if stack has any values
if stack:
return False
return True
if __name__ == "__main__":
parenthesis_expression = "{[()]}"
if parenthesis_checker(parenthesis_expression):
print("expression is balanced")
else:
print("expression is not balanced")
```

**C++**

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool parenthesis_checker(string parenthesis_expression) {
stack<char> stack1;
for (int i = 0; i < parenthesis_expression.size(); i++) {
if (
parenthesis_expression[i] == '(' ||
parenthesis_expression[i] == '{' ||
parenthesis_expression[i] == '['
) {
stack1.push(parenthesis_expression[i]);
} else {
if (!stack1.empty()) {
char top = stack1.top();
if (top == '(' && parenthesis_expression[i] == ')' ||
top == '{' && parenthesis_expression[i] == '}' ||
top == '[' && parenthesis_expression[i] == ']'
) {
stack1.pop();
} else {
return false;
}
} else {
return false;
}
}
}
if (stack1.empty())
return true;
else
return false;
}
int main() {
string parenthesis_expression = "{[()]}";
if(parenthesis_checker(parenthesis_expression))
cout << "expression is balanced";
else
cout << "expression is not balanced";
return 0;
}
```

**Java**

```
import java.util.*;
class Solution {
public static boolean parenthesis_checker(String parenthesis_expression) {
Stack<String> stack = new Stack<>();
for (int i = 0; i < parenthesis_expression.length(); i++) {
String parenthesis = String.valueOf(parenthesis_expression.charAt(i));
if ("(".equals(parenthesis) ||
"{".equals(parenthesis) ||
"[".equals(parenthesis) ) {
stack.push(parenthesis);
continue;
}
if (stack.empty()) {
return false;
}
if (")".equals(parenthesis)) {
if ("(".equals(stack.pop())) {
continue;
} else {
return false;
}
}
if ("}".equals(parenthesis)) {
if ("{".equals(stack.pop())) {
continue;
} else {
return false;
}
}
if ("]".equals(parenthesis)) {
if ("[".equals(stack.pop())) {
continue;
} else {
return false;
}
}
}
if (stack.empty()) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
String parenthesis_expression = "{[()]}";
if(parenthesis_checker(parenthesis_expression))
System.out.println("expression is balanced");
else
System.out.println("expression is not balanced");
}
}
```

### Output

`expression is balanced`

### Time Complexity

The **time complexity** of the parenthesis checker implementation using stack is `O(n)`

where `n`

is the length of the input expression, as we are traversing the string character by character using for loop.

### Space Complexity

The space complexity of the parenthesis checker implementation using stack is `O(n)`

where `n`

is the length of the input expression, as we are storing the opening parenthesis characters in a stack.

## Algorithm 2 – Pointer Based Approach

In this approach, the parenthesis checker is implemented using a **pointer** to last unmatched open parenthesis.

### Algorithm

The algorithm has the following steps:

- Set pointer top to –
`1`

at initialization. **Traverse**through the input string expression character by character.- Increase top by one, if
`top < 0`

or the current character does not match the open bracket at the top index (as the current character is the most recently occurred open bracket). - Else, decrement the top pointer by one, if the current character matches the open bracket at the top index ( now it is pointing to the open bracket that is not matched yet).

- Increase top by one, if
- If the top pointer falls to –
`1`

after iterating all characters, then all open brackets are matched with their corresponding closing bracket in the correct sequence ( i.e., the**string is a valid parenthesis expression**)

### Code Implementation

**Python**

```
def is_match(a, b):
parenthesis_pairs = { '(': ')',
'{': '}',
'[': ']' }
try:
if parenthesis_pairs[a] == b:
return True
except:
pass
return False
def parenthesis_checker(parenthesis_expression):
parenthesis_expression = list(parenthesis_expression)
top = -1
for i in range(len(parenthesis_expression)):
if top < 0 or not is_match(parenthesis_expression[top], parenthesis_expression[i]):
top += 1
parenthesis_expression[top] = parenthesis_expression[i]
else:
top -= 1
return top == -1
parenthesis_expression = "{[()]}"
if parenthesis_checker(parenthesis_expression):
print("expression is balanced")
else:
print("expression is not balanced")
```

**C++**

```
#include <iostream>
using namespace std;
bool is_match(char a, char b) {
if (a == '(' && b == ')')
return true;
if (a == '[' && b == ']')
return true;
if (a == '{' && b == '}')
return true;
return false;
}
bool parenthesis_checker(string parenthesis_expression) {
int top = -1;
for (int i = 0; i < parenthesis_expression.length(); i++) {
if (top < 0 || !is_match(parenthesis_expression[top], parenthesis_expression[i])) {
++top;
parenthesis_expression[top] = parenthesis_expression[i];
}
else
--top;
}
return top == -1;
}
int main() {
string parenthesis_expression = "{[()]}";
if(parenthesis_checker(parenthesis_expression))
cout << "expression is balanced";
else
cout << "expression is not balanced";
return 0;
}
```

**Java**

```
class Main{
static boolean is_match(char a, char b) {
if (a == '(' && b == ')')
return true;
if (a == '[' && b == ']')
return true;
if (a == '{' && b == '}')
return true;
return false;
}
static boolean parenthesis_checker(String string_expression) {
int top = -1;
char parenthesis_expression[] = new char[string_expression.length()];
for (int i = 0; i < string_expression.length(); i++) {
parenthesis_expression[i] = string_expression.charAt(i);
}
for (int i = 0; i < string_expression.length(); i++) {
if (top < 0 || !is_match(parenthesis_expression[top], parenthesis_expression[i])) {
top++;
parenthesis_expression[top] = parenthesis_expression[i];
} else {
top--;
}
}
return top == -1;
}
public static void main(String[] args) {
String parenthesis_expression = "{[()]}";
if (parenthesis_checker(parenthesis_expression))
System.out.println("expression is balanced");
else
System.out.println("expression is not balanced");
}
}
```

### Output

`expression is balanced`

### Time Complexity

The **time complexity** of the parenthesis checker implementation using stack is $O(n)$ where `n`

is the length of the input expression, as we are traversing the string character by character using for loop.

### Space Complexity

The space complexity of the parenthesis checker implementation using stack is $O(1)$, as we are using only one integer pointer.

## Conclusion

In this article we have understood:

- A
**Parenthesis checker**is a parenthesis balance checking algorithm. - The use cases of input and output examples for parenthesis checker.
- Two approaches for implementing parenthesis checker:
**Stack-based approach**and**Pointer-based approach**. - Wrote code implementation using
`C++`

,`Python`

, and`Java`

for both approaches. - In
**stack based approach**the time complexity is $O(n)$ and the space complexity is $O(n)$ since we create a stack. - In the
**pointer-based approach**, the time complexity is $O(n)$ and the space complexity is $O(1)$ since only one single pointer is used.