Balanced parentheses using Stack

One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched. Here are some of the balanced and unbalanced expressions.

Consider the above mentioned unbalanced expressions,

• The first expression ( a + b is unbalanced as there is no closing parenthesis given.
• The second expression [ ( c - d  * e ] is unbalanced as the closed round parenthesis is not given.
• The third expression { [ ( ] ) } is unbalanced as the nesting of square parenthesis and the round parenthesis are incorrect.

Steps to find whether a given expression is balanced or unbalanced

• Input the expression and put it in a character stack.
• Scan the characters from the expression one by one.
1. If the scanned character is a starting bracket ( ‘ ( ‘ or ‘ { ‘ or ‘ [ ‘), then push it to the stack.
2. If the scanned character is a closing bracket ( ‘ ) ’  or ‘ } ’  or ‘ ] ’ ), then pop from the stack and if the popped character is the equivalent starting bracket, then proceed. Else, the expression is unbalanced.
•  After scanning all the characters from the expression, if there is any parenthesis found in the stack or if the stack is not empty, then the expression is unbalanced.
• Now, let us see a program to check balanced parentheses in the given expression.

C program to check balanced parentheses using stack

`#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 20struct stack{char stk[MAX];int top;}s;void push(char item){if (s.top == (MAX - 1))printf ("Stack is Full\n");else{s.top = s.top + 1; // Push the char and increment tops.stk[s.top] = item;}}void pop(){if (s.top == - 1){printf ("Stack is Empty\n");}else{s.top = s.top - 1; // Pop the char and decrement top}}int main(){char exp[MAX];int i = 0;s.top = -1;printf("\nINPUT THE EXPRESSION : ");scanf("%s", exp);for(i = 0;i < strlen(exp);i++){if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{'){push(exp[i]); // Push the open bracketcontinue;}else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}') // If a closed bracket is encountered{if(exp[i] == ')'){if(s.stk[s.top] == '('){pop(); // Pop the stack until closed bracket is found}else{printf("\nUNBALANCED EXPRESSION\n");break;}}if(exp[i] == ']'){if(s.stk[s.top] == '['){pop(); // Pop the stack until closed bracket is found}else{printf("\nUNBALANCED EXPRESSION\n");break;}}if(exp[i] == '}'){if(s.stk[s.top] == '{'){pop(); // Pop the stack until closed bracket is found}else{printf("\nUNBALANCED EXPRESSION\n");break;}}}}if(s.top == -1){printf("\nBALANCED EXPRESSION\n"); // Finally if the stack is empty, display that the expression is balanced}}`

OUTPUT

Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`