Check for Balanced Bracket expression without using stack

Check for Balanced Bracket expression using Stack:

Following are the steps to be followed:

Initialize a variable i with -1.
Iterate through the string and
- If it is an open bracket then increment the counter by 1 and replace i^th character of the string with the opening bracket.
- Else if it is a closing bracket of the same corresponding opening bracket (opening bracket stored in exp[i]) then decrement i by 1.
At last, if we get i = -1, then the string is balanced and we will return true. Otherwise, the function will return false.

Below is the implementation of the above approach:

C++

#include <iostream>
 
using namespace std;
 
 bool areBracketsBalanced(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 expr = "{()}[]";
 
    // Function call
    if (areBracketsBalanced(expr))
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

Java

public class GFG {
    public static boolean areBracketsBalanced(String s)
    {
        int i = -1;
        char[] stack = new char[s.length()];
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[')
                stack[++i] = ch;
            else {
                if (i >= 0
                    && ((stack[i] == '(' && ch == ')')
                        || (stack[i] == '{' && ch == '}')
                        || (stack[i] == '[' && ch == ']')))
                    i--;
                else
                    return false;
            }
        }
        return i == -1;
    }
 
    public static void main(String[] args)
    {
        String expr = "{()}[]";
 
        // Function call
        if (areBracketsBalanced(expr))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

C#

// c# implementation
 
using System;
 
public class GFG {
    static bool areBracketsBalanced(string s) {
        int i = -1;
        char[] stack = new char[s.Length];
        foreach (char ch in s) {
            if (ch == '(' || ch == '{' || ch == '[')
                stack[++i] = ch;
            else {
                if (i >= 0 && ((stack[i] == '(' && ch == ')') || (stack[i] == '{' && ch == '}') || (stack[i] == '[' && ch == ']')))
                    i--;
                else
                    return false;
            }
        }
        return i == -1;
    }
 
    static void Main() {
        string expr = "{()}[]";
 
        // Function call
        if (areBracketsBalanced(expr))
            Console.WriteLine("Balanced");
        else
            Console.WriteLine("Not Balanced");
    }
}
// ksam24000

Python3

def are_brackets_balanced(s):
    stack = []
    for ch in s:
        if ch in ('(', '{', '['):
            stack.append(ch)
        else:
            if stack and ((stack[-1] == '(' and ch == ')') or
                          (stack[-1] == '{' and ch == '}') or
                          (stack[-1] == '[' and ch == ']')):
                stack.pop()
            else:
                return False
    return not stack
 
expr = "{()}[]"
 
# Function call
if are_brackets_balanced(expr):
    print("Balanced")
else:
    print("Not Balanced")

Javascript

function areBracketsBalanced(s) {
    let i = -1;
    let stack = [];
    for (let ch of s) {
        if (ch === '(' || ch === '{' || ch === '[') {
            stack.push(ch);
            i++;
        } else {
            if (i >= 0 && ((stack[i] === '(' && ch === ')') || (stack[i] === '{' && ch === '}') || (stack[i] === '[' && ch === ']'))) {
                stack.pop();
                i--;
            } else {
                return false;
            }
        }
    }
    return i === -1;
}
 
let expr = "{()}[]";
 
// Function call
if (areBracketsBalanced(expr))
    console.log("Balanced");
else
    console.log("Not Balanced");

Output

Balanced

Time Complexity: O(N), Iteration over the string of size N one time.
Auxiliary Space: O(1)

Check for Balanced Brackets in an expression (well-formedness)

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.

Example:

Input: exp = “[()]{}{[()()]()}”
Output: Balanced
Explanation: all the brackets are well-formed

Input: exp = “[(])”
Output: Not Balanced
Explanation: 1 and 4 brackets are not balanced because
there is a closing ‘]’ before the closing ‘(‘

Tags:

#Amazon #Hike #Oracle #Parentheses-Problems #Snapdeal #Walmart #Wipro #Yatra.com #Zoho #DSA #Stack #Strings #Amazon #Hike #Oracle #Snapdeal #Walmart #Wipro #Yatra.com #Zoho #Stack #Strings