Question

Describe an O(n)-time algorithm that checks if brackets in a given arithmetic expression is properly placed, i.e., all left brackets are matched with their right counterparts and there are no unmatched brackets between any pair of matched brackets. Note that there are generally more than one types of brackets and only those of the same type can match against each other. For simplicity, you can assume that all operands are represented as ‘a’ and addition, +, is the only available operation. See below for examples of expressions, where brackets are improperly used:

(a + a) + a), (a + (a +a), ((a + ) a), a + {a + (a + a)), a + [a + (a + a] + a) Your algorithm must be non-recursive and may use a stack.

C++

Answer 1

Algorithm:

• Declare a character stack S.
• Now traverse the expression string exp.
  1. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
  2. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
• After complete traversal, if there is some starting bracket left in stack then “not balanced”

// CPP program to check for balanced parenthesis. 
#include <bits/stdc++.h> 
using namespace std; 

// function to check if paranthesis are balanced 
bool areParanthesisBalanced(string expr) 
{ 
        stack<char> s; 
        char x; 

        // Traversing the Expression 
        for (int i = 0; i < expr.length(); i++) { 
                if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') { 
                        // Push the element in the stack 
                        s.push(expr[i]); 
                        continue; 
                } 

                // IF current current character is not opening 
                // bracket, then it must be closing. So stack 
                // cannot be empty at this point. 
                if (s.empty()) 
                        return false; 

                switch (expr[i]) { 
                case ')': 

                        // Store the top element in a 
                        x = s.top(); 
                        s.pop(); 
                        if (x == '{' || x == '[') 
                                return false; 
                        break; 

                case '}': 

                        // Store the top element in b 
                        x = s.top(); 
                        s.pop(); 
                        if (x == '(' || x == '[') 
                                return false; 
                        break; 

                case ']': 

                        // Store the top element in c 
                        x = s.top(); 
                        s.pop(); 
                        if (x == '(' || x == '{') 
                                return false; 
                        break; 
                } 
        } 

        // Check Empty Stack 
        return (s.empty()); 
} 

// Driver program to test above function 
int main() 
{ 
        string expr = "{()}[]"; 

        if (areParanthesisBalanced(expr)) 
                cout << "Balanced"; 
        else
                cout << "Not Balanced"; 
        return 0; 
} 

Time Complexity: O(n)
Auxiliary Space: O(n) for stack.