Check for Balanced Parentheses in an Expression

Last Updated on May 11, 2023 by Prepbytes

In computer science, balanced parentheses are a common requirement for many programming languages and applications. Balanced parentheses refer to an expression in which all opening and closing parentheses are properly matched and nested. A balanced expression ensures that the program can be executed without any errors.

To check for balanced brackets in an expression using stack in C programming, you need to traverse the expression and keep track of the opening and closing parentheses using a stack data structure. If an opening parenthesis is encountered, it is pushed onto the stack, and if a closing parenthesis is encountered, it is compared with the top element of the stack.

If the closing parenthesis matches the top element, the top element is popped, and the traversal continues. If the closing parenthesis does not match the top element or there are no more elements in the stack, the expression is considered unbalanced.

How to Check for Balanced Parentheses in an Expression

Given an expression containing only ‘(‘, ’)’, ’{‘, ‘}’, ‘[‘, ‘]’ , check whether the expression is balanced or not.

An expression is balanced if each opening bracket is closed by the same type of closing bracket in the exact same order.

Input:

A string representing the given expression

Output:

Boolean value

Test cases:
Input 1:

“({[]})”

Output 1:

true

Input 2:

“(){}](“

Output 2:

false

Approach – Check for Balanced Brackets in an Expression using Stack

The idea is to use the LIFO functionality of the stack. As a stack is LIFO data structure, we will remove every opening bracket (‘(‘, ‘{‘, ‘[‘), whenever we encounter the same type of closing bracket (‘)’, ‘}’, ‘]’).
If for any opening bracket we don’t have a closing bracket, the opening bracket will remain in the stack forever.
Similarly if we only have a closing bracket without a preceding opening bracket we will just push the closing bracket into the stack and it will remain there forever.
So, at last after traversing the whole expression, if the stack is empty then it will mean that the given expression is balanced, otherwise if the stack contains elements that would mean the given expression was unbalanced.

Algorithm to Check Balanced Parentheses in C using Stack

1. Initialize an empty stack.
2. Iterate i from 0 to length(expression).
   • Store the current character in a variable ‘ch’.
   • If stack is empty: Push ‘ch’ to the stack
   • Else if current character is a closing bracket and of the top of the stack contains an opening bracket of the same type then remove the top of the stack: Else, push ‘ch’ to the stack
3. If the stack is empty, return true, else false.

Dry Run to Check for Balanced Brackets in an Expression using Stack

Input:

“({[]})”

Output:

true

As the stack is empty, hence the given expression was balanced.

Code Implementation

import java.util.*;
public class Main
{
	public static void main(String[] args) {
		String exp = "({[]})";
		System.out.println(isBalanced(exp));
	}
	// Function to check whether given expression is balanced or not
	public static boolean isBalanced(String exp) {
        Stack<Character> st = new Stack<>();
        
        // Traverse over the expression
        for(int i = 0; i < exp.length(); i++){
            
            // Get the current character 
            char ch = exp.charAt(i);
            
            // If the stack is empty, push the current character into the stack
            if(st.isEmpty()){
                st.push(ch);
            }
            
            // Otherwise if the current character is a closing bracket 
            // and of the top of the stack contains an opening bracket of the same type
            // then remove the top of the stack
            else if((ch==')' && st.peek() == '(')||(ch=='}' && st.peek() == '{')||(ch==']' && st.peek() == '[')){
                st.pop();
            }
            else{
                st.push(ch);
            }      
        }
        
        // If after traversing the whole expression the stack is empty
        // then it means the given expression is balanced else unbalanced
        return (st.isEmpty());
    }
}

Output:
true

Time complexity: O(n). We can observe that every character is pushed and removed from the stack at most once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity.

Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is also O(n) as we are using a stack. At any point of time the stack can contain at most n elements.

Conclusion
In conclusion, checking for balanced parentheses in an expression using stack is a crucial concept in computer science. A balanced expression ensures that the program can be executed without any errors, making it a crucial step in many applications such as compilers, parsers, and data validation.

Overall, understanding how to check for balanced parentheses using a stack in C programming is an essential skill for programmers and computer science students. It forms the foundation for many advanced concepts in computer science and is used in many real-world applications.

Frequently Asked Questions

Q1. What is a stack, and why is it used to check for balanced parentheses?
Ans. A stack is a data structure that stores elements in a last-in, first-out (LIFO) order. It is used to check for balanced parentheses because it allows us to keep track of opening and closing parentheses in an expression and ensure that they are properly matched and nested.

Q2. How do you implement a stack in C programming?
Ans. A stack can be implemented in C programming using an array or a linked list. The array-based implementation is simpler and more efficient but has a fixed size, while the linked list implementation is more flexible but requires more memory and overhead.

Q3. What is the time complexity of checking for balanced parentheses using a stack?
Ans. The time complexity of checking for balanced parentheses using a stack is O(n), where n is the length of the expression. This is because we need to traverse the entire expression once and perform constant time operations on the stack for each character.

Q4. Can a stack be used to check for balanced parentheses in other languages besides C?
Ans. Yes, a stack can be used to check for balanced parentheses in other programming languages as well, including Java, Python, and JavaScript.

Q5 . What is the difference between balanced parentheses and balanced brackets?
Ans. Balanced parentheses refer to an expression in which all opening and closing parentheses are properly matched and nested, while balanced brackets refer to an expression in which all opening and closing brackets (e.g., [], {}) are properly matched and nested.