Given a string containing opening and closing braces, check if it represents a balanced expression or not.

For example,

{[{}{}]}[()], {{}{}}, []{}() are balanced expressions.
 
{()}[), {(}) are not balanced.

Practice this problem

We can use a stack to solve this problem. The idea is to traverse the given expression, and

  • If the current character in the expression is an opening brace ( or { or [, push it into the stack.
  • If the current character in the expression is a closing brace ) or } or ], pop a character from the stack, and return false if the popped character is not the same as the current character, or it does not pair with the current character of the expression. Also, if the stack is empty, the total number of opening braces is less than the closing brace number at that point, so the expression cannot be balanced.

This would translate to a simple code below in C++, Java, and Python:

C++


Download  Run Code

Output:

The expression is balanced

Java


Download  Run Code

Output:

The expression is balanced

Python


Download  Run Code

Output:

The expression is balanced

Another good solution traverses the given expression, and for each opening brace in the expression, push the corresponding closing brace into the stack. If the expression’s current character is a closing brace, it should match the stack’s top element. If a match is found, pop the top character from the stack; otherwise, we can say that the expression is not balanced. Also, note that the stack should be empty after we have processed all characters in the expression.

This would translate to a simple code below in C++, Java, and Python:

C++


Download  Run Code

Output:

The expression is balanced

Java


Download  Run Code

Output:

The expression is balanced

Python


Download  Run Code

Output:

The expression is balanced

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the input expression.