Stack: Check if valid parentheses in an expression

Problem Statement:

Given a string “s” contains various types of brackets.

You need to check if the brackets are balanced or not.

Example:

Input: s = “[{()}]”
Output: true

Solution Explanation:

Take a temp stack.

Traverse the string from left to right.

If the character is opening bracket, push into the stack.

It the character is a closing bracket, and closing bracket matches with opening bracket, pop the opening bracket, else expression is not balanced.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

bool solution(const string& s) 
{
  
    stack<char> st;

    for (int i = 0; i < s.length(); i++) 
    {
        
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') 
        {
            st.push(s[i]); 
        } 
      
        else 
        {

            if (!st.empty() && 
                ((st.top() == '(' && s[i] == ')') ||
                 (st.top() == '{' && s[i] == '}') ||
                 (st.top() == '[' && s[i] == ']'))) 
            {

                st.pop(); 
            }
            else 
            {
                
                return false; 
            }
        }
    }
    
    return st.empty();
}

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

    if (solution(s))
        cout << "true";
    else
        cout << "false";
    return 0;
}

Output

True