Check for Balanced Parentheses in an Expression

Introduction

Balanced parentheses mean that opening brackets and closing brackets maintain proper order logically. Checking for balanced parentheses is one of the popular problems asked in coding interviews. We will explain the approach for solving this problem as well as the intuition behind it.

What are Balanced Parentheses?

Balanced parentheses is a sequence of parenthesis in which for every opening parenthesis, there is a corresponding closing parenthesis of the same type. Also the parenthesis sequence must be nested properly. For example {[{}]} is a balanced parenthesis whereas {[(])} is not a balanced parenthesis.

Problem statement of String Expression of Parentheses

You are given a string expression of parentheses, containing the characters “(”, ”)”, ”{“, ”}”, “[“, “]”. The expression is balanced if

Open brackets are closed by the same type of closing brackets.
Open brackets must be closed in the correct order of their occurrence.

Check if the given expression is balanced or not.

Example

Input

exp="{ ( ) [ ] }"

Output

the given expression is balanced

Explanation

For the given expression, open brackets are closed by the same type of closing brackets in proper order.

Note: Please try to solve the problem first and then see the below solution approach.

Approaches in Balanced Parentheses

There are a few approaches that can be used to solve the problem. One easier approach is a stack-based approach where space complexity is O(n) and time complexity is also O(n).

But here, in the desired approach, space complexity should be O(1). So, no extra space can be used.

Check for Balanced Bracket expression using Stack:

Let's take an example. Here we have the input string s with its output:

Input: s = "{()[]}"

Output: true

The approach is quite simple if we find an opening bracket("(,{,["), then we will simply store it in the stack. If we found a closing bracket, then first, we will check if our stack is empty or not; if it's empty, then we will simply return false since a closing bracket cannot come if there is no opening bracket. Also, if the stack is not empty, then we will check if the top element of our stack is matching to our closing bracket or not; if not, simply return false. At last, if everything is fine, return true.

Code implementation

Let's implement the code:

C++
Java
Python
C#
JavaScript

C++

#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '{' || ch == '[') {
            st.push(ch);
        } else {
            if (st.empty() || (st.top() != '(' && ch == ')') ||
                (st.top() != '{' && ch == '}' ) ||
                (st.top() != '[' && ch == ']')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string s="{()[]}";

    if (isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Stack;

public class Main {

    public static boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                st.push(ch);
            } else {
                if (st.isEmpty() || (st.peek() != '(' && ch == ')') ||
                    (st.peek() != '{' && ch == '}') ||
                    (st.peek() != '[' && ch == ']')) {
                    return false;
                }
                st.pop();
            }
        }
        return st.isEmpty();
    }

    public static void main(String[] args) {
        String s = "{()[]}";
        if (isValid(s)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def isValid(s):
    stack = []
    for ch in s:
        if ch in ['(', '{', '[']:
            stack.append(ch)
        else:
            if not stack or (stack[-1] != '(' and ch == ')') or \
               (stack[-1] != '{' and ch == '}') or \
               (stack[-1] != '[' and ch == ']'):
                return False
            stack.pop()
    return not stack

# Example usage
s = "{()[]}"
if isValid(s):
    print("true")
else:
    print("false")

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class Program
{
    public static bool IsValid(string s)
    {
        Stack<char> st = new Stack<char>();
        foreach (char ch in s)
        {
            if (ch == '(' || ch == '{' || ch == '[')
            {
                st.Push(ch);
            }
            else
            {
                if (st.Count == 0 || (st.Peek() != '(' && ch == ')') ||
                    (st.Peek() != '{' && ch == '}') ||
                    (st.Peek() != '[' && ch == ']'))
                {
                    return false;
                }
                st.Pop();
            }
        }
        return st.Count == 0;
    }

    static void Main()
    {
        string s = "{()[]}";
        if (IsValid(s))
        {
            Console.WriteLine("true");
        }
        else
        {
            Console.WriteLine("false");
        }
    }
}

JavaScript

function isValid(s) {
    let stack = [];
    for (let ch of s) {
        if (ch === '(' || ch === '{' || ch === '[') {
            stack.push(ch);
        } else {
            if (stack.length === 0 || (stack[stack.length - 1] !== '(' && ch === ')') ||
                (stack[stack.length - 1] !== '{' && ch === '}') ||
                (stack[stack.length - 1] !== '[' && ch === ']')) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.length === 0;
}

// Example usage
let s = "{()[]}";
console.log(isValid(s) ? "true" : "false");

You can also try this code with Online Javascript Compiler

Run Code

Output:

true

Check for Balanced Bracket expression without using stack :

Let's take an example. Here we have the input string s with its output:

Input: s = "[()]{}{[()()]()}"

Output: true

The approach is we will use a variable "i" initialized with -1. Then we loop through a given string character by character. If we encounter an opening bracket, we increase the value of "i" by 1 and replace the "i-th" character of the string with the opening bracket. On the other hand, if we come across a closing bracket that matches the corresponding opening bracket stored at index "i", we decrease the value of "i" by 1.

If "i" is not -1 at the end, it means that there is at least one unbalanced bracket, so returns false or else true.

Code implementation

C++
Python
C#
JavaScript
Java

C++

#include <iostream>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        int i = -1;
        for (auto &ch : s) {
            if (ch == '(' || ch == '{' || ch == '[') {
                s[++i] = ch;
            } else {
                if (i >= 0 &&
                    ((s[i] == '(' && ch == ')') || (s[i] == '{' && ch == '}' ) ||
                    (s[i] == '[' && ch == ']'))) {
                    i--;
                } else {
                    return false;
                }
            }
        }
        return i == -1;
    }
};

int main() {
    string s="[()]{}{[()()]()}";

    if (Solution().isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

class Solution:
    def isValid(self, s: str) -> bool:
        i = -1
        for ch in s:
            if ch in ['(', '{', '[']:
                i += 1
                s = s[:i] + ch + s[i + 1:]  # Update the string at index i
            else:
                if i >= 0 and (
                    (s[i] == '(' and ch == ')') or
                    (s[i] == '{' and ch == '}') or
                    (s[i] == '[' and ch == ']')):
                    i -= 1
                else:
                    return False
        return i == -1

# Example usage
s = "[()]{}{[()()]()}"
if Solution().isValid(s):
    print("true")
else:
    print("false")

You can also try this code with Online Python Compiler

Run Code

C#

using System;

class Solution
{
    public bool IsValid(string s)
    {
        int i = -1;
        char[] chars = s.ToCharArray();
        foreach (char ch in chars)
        {
            if (ch == '(' || ch == '{' || ch == '[')
            {
                chars[++i] = ch;
            }
            else
            {
                if (i >= 0 && ((chars[i] == '(' && ch == ')') ||
                               (chars[i] == '{' && ch == '}') ||
                               (chars[i] == '[' && ch == ']')))
                {
                    i--;
                }
                else
                {
                    return false;
                }
            }
        }
        return i == -1;
    }

    static void Main()
    {
        string s = "[()]{}{[()()]()}";
        if (new Solution().IsValid(s))
        {
            Console.WriteLine("true");
        }
        else
        {
            Console.WriteLine("false");
        }
    }
}

JavaScript

class Solution {
    isValid(s) {
        let i = -1;
        const chars = s.split('');
        for (let ch of chars) {
            if (ch === '(' || ch === '{' || ch === '[') {
                chars[++i] = ch;
            } else {
                if (i >= 0 && (
                    (chars[i] === '(' && ch === ')') ||
                    (chars[i] === '{' && ch === '}') ||
                    (chars[i] === '[' && ch === ']'))) {
                    i--;
                } else {
                    return false;
                }
            }
        }
        return i === -1;
    }
}

// Example usage
const s = "[()]{}{[()()]()}";
console.log(new Solution().isValid(s) ? "true" : "false");

You can also try this code with Online Javascript Compiler

Run Code

Java

public class Solution {
    public boolean isValid(String s) {
        int i = -1;
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (ch == '(' || ch == '{' || ch == '[') {
                chars[++i] = ch;
            } else {
                if (i >= 0 && ((chars[i] == '(' && ch == ')') ||
                               (chars[i] == '{' && ch == '}') ||
                               (chars[i] == '[' && ch == ']'))) {
                    i--;
                } else {
                    return false;
                }
            }
        }
        return i == -1;
    }

    public static void main(String[] args) {
        String s = "[()]{}{[()()]()}";
        if (new Solution().isValid(s)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

true

Frequently Asked Questions

How do you check balanced parentheses in an expression?

To check balanced parentheses, use a stack data structure. Iterate through the expression, push opening parentheses onto the stack, and pop for each closing parenthesis, ensuring the stack is empty at the end.

What is the balanced parentheses problem?

The balanced parentheses problem involves verifying if a given expression has matching open and close parentheses.

What are balanced parentheses in Java?

In Java, balanced parentheses are ensured using a stack. Iterate through the expression, push for opening parentheses, and pop for closing ones, ensuring the stack is empty at the end.

What is the importance of balanced parenthesis as an application of stack?

Balanced parentheses are crucial in programming languages, compilers, and expression evaluation. They ensure that expressions are correctly structured, enabling proper parsing and execution. Using a stack data structure effectively checks for balanced parentheses by pushing opening brackets and popping them upon encountering matching closing brackets.

Conclusion

This article has covered the best way to check for balanced parentheses in an expression. You might also want to try the stack-based approach, as it makes the process easier by allowing extra space for storage