Posted on by Kalkicode
Code Stack

# Check Balanced parentheses using Stack

The problem is to check if a given string of parentheses is balanced or not using a stack. A string is considered balanced if every opening parenthesis has a corresponding closing parenthesis and they appear in the correct order.

## Example

1. For the input string "[()]{}{()()}", the parentheses are balanced as every opening parenthesis has a corresponding closing parenthesis in the correct order.
2. For the input string "(()){}{}[{]}", the parentheses are not balanced as there is a mismatch between the opening and closing parentheses.

## Idea to Solve the Problem

To check if the parentheses are balanced, we will use a stack data structure. We will traverse the given string character by character:

1. If the character is an opening parenthesis ('{', '[', or '('), we will push it onto the stack.
2. If the character is a closing parenthesis ('}', ']', or ')'), we will check if the stack is not empty. If the stack is not empty, we will pop the top element from the stack and compare it with the current closing parenthesis. If they match, it means the current closing parenthesis has a corresponding opening parenthesis, and we continue with the next character.
3. If the stack is empty when we encounter a closing parenthesis or if the top element of the stack does not match the current closing parenthesis, the parentheses are not balanced, and we can stop the traversal.
4. After traversing the entire string, if the stack is empty, it means all the opening parentheses had corresponding closing parentheses, and the parentheses are balanced; otherwise, they are not balanced.

## Algorithm

1. Define a structure for the stack node `struct MyStack`, containing a character data value and a pointer to the next node.
2. Define a global pointer `top` for the stack, initialized to NULL.
3. Create a function `push` to add characters to the stack. Create a new stack node and set its `data` to the provided character. Then push the new node onto the stack.
4. Create a function `pop` to remove characters from the stack. If the stack is not empty, remove the top node, free the memory, and update the top.
5. Create a function `parentheses` to check if the parentheses are balanced or not. Traverse the string, and for each character:
• If it is an opening parenthesis, push it onto the stack.
• If it is a closing parenthesis, check if the stack is not empty and if the top element of the stack matches the current closing parenthesis. If they match, pop the top element; otherwise, the parentheses are not balanced, and we can stop.
• If the stack is empty when encountering a closing parenthesis, the parentheses are not balanced, and we can stop.
6. After traversing the entire string, check if the stack is empty. If it is empty, print "Balanced"; otherwise, print "Not Balanced".

## Pseudocode

``````FUNCTION push(data):
node = new MyStack
node.data = data
node.next = top
top = node

FUNCTION pop():
IF top is not NULL:
node = top
top = top.next
free(node)

FUNCTION parentheses(str, size):
status = 1
FOR i = 0 TO size AND status = 1:
IF str[i] is '{' OR str[i] is '[' OR str[i] is '(':
push(str[i])
ELSE IF top is not NULL:
IF (str[i] is '}' AND top.data is '{') OR
(str[i] is ']' AND top.data is '[') OR
(str[i] is ')' AND top.data is '('):
pop()
ELSE:
status = 0
ELSE:
status = 0
IF status is 1 AND top is NULL:
PRINT "Balanced"
ELSE:
PRINT "Not Balanced"
WHILE top is not NULL:
pop()

FUNCTION main():
str1 = "[()]{}{[()()]()}"
s = size of str1 - 1
PRINT str1
parentheses(str1, s)

str2 = "(())[](){}{}[{]}"
s = size of str2 - 1
PRINT str2
parentheses(str2, s)
``````

## Code Solution

``````//C Program
//Check Balanced parentheses using Stack
#include <stdio.h>
#include <stdlib.h>
struct MyStack{

char data;
struct MyStack*next;
};

struct MyStack*top=NULL;

//Add a new element in stack
void push(char data)
{
//Make a new stack node
struct MyStack*node = (struct MyStack*)malloc(sizeof(struct MyStack));
if(node!=NULL)
{
node->data = data;
node->next = top;
top = node;
}
else
{
printf("Memory overflow\n");
}
}
//Add a top element in stack
void pop()
{
if(top!=NULL)
{
struct MyStack*node = top;
top = top->next;
free(node);
node=NULL;
}
}
void parentheses(char str[],int size)
{
int status=1;

for (int i = 0; i < size && status == 1; ++i)
{

if(str[i]=='{'||str[i]=='['||str[i]=='(')
{
push(str[i]);
}
else if(top !=NULL )
{

if((str[i]=='}' && top->data =='{')||
(str[i]==']' && top->data =='[')||
(str[i]==')' && top->data=='(') )
{
//Remove a stack element
pop();
}
else
{
//If in case parentheses are not Balanced
status=0;
}
}
else
{
status=0;

}

}
if(status==1 &&  top == NULL)
{
printf("Balanced\n");
}
else
{
printf("Not Balanced\n");
}

//In case stack are not empty
//Then remove its elements
while(top!=NULL)
{
pop();
}

}
int main()
{
//Test Case
char str1[]="[()]{}{[()()]()}";
int s=sizeof(str1)/sizeof(str1[0]);
printf("%s\n",str1 );
parentheses(str1,s-1);

char str2[]="(())[](){}{}[{]}";
s=sizeof(str2)/sizeof(str2[0]);
printf("%s\n",str2 );
parentheses(str2,s-1);

return 0;
}```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````/*
Java Program
Check Balanced parentheses using Stack
*/
//Stack Node
class Node
{
public char data;
public Node next;
public Node(char data)
{
this.data = data;
next = null;
}
}
public class MyStack {
public Node top;
public MyStack()
{
top = null;
}
//Add a new element in stack
public void push(char data)
{
//Make a new stack node
Node new_node = new Node(data);
if(new_node!=null)
{
new_node.next=top;
top = new_node;
}
else
{
System.out.print("Memory overflow\n");
}
}
//Add a top element in stack
public void pop()
{
if(top!=null)
{
top = top.next;
}
}
public void parentheses(String str,int size)
{
boolean status = true;

for (int i = 0; i < size && status == true; ++i)
{

if(str.charAt(i)=='{'||str.charAt(i)=='['||str.charAt(i)=='(')
{
push(str.charAt(i));

}
else if(top != null )
{

if((str.charAt(i)=='}' && top.data =='{')||
(str.charAt(i)==']' && top.data =='[')||
(str.charAt(i)==')' && top.data=='(') )
{
//Remove a stack element
pop();
}
else
{

//If in case parentheses are not Balanced
status=false;
}
}
else
{
status=false;
}

}
if(status==true && top == null)
{
System.out.print("\nBalanced\n");
}
else
{
System.out.print("\nNot Balanced\n");
}

//In case stack are not empty
//Then remove its elements
while(top!=null)
{
pop();
}

}
public static void main(String[] args) {

MyStack obj = new MyStack();

String str = "[()]{}{[()()]()}";

System.out.print(str);

obj.parentheses(str,str.length());

str = "(())[](){}{}[{]}";

System.out.print(str);

obj.parentheses(str,str.length());

}
}```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced
``````
``````/*
C++ Program
Check Balanced parentheses using Stack
*/
//Stack Node
#include<iostream>

using namespace std;
class Node {
public:
char data;
Node *next;
Node(char data) {
this->data = data;
this->next = NULL;
}
};
class MyStack {
public:
Node *top;
MyStack() {
this->top = NULL;
}
//Add a new element in stack
void push(char data) {
//Make a new stack node
Node *new_node = new Node(data);
if (new_node != NULL) {
new_node->next = this->top;
this->top = new_node;
} else {
cout << "Memory overflow\n";
}
}
//Add a top element in stack
void pop() {
if (this->top != NULL) {
this->top = this->top->next;
}
}
void parentheses(string str, int size) {
bool status = true;
for (int i = 0; i < size &&
status == true; ++i) {
if (str[i] == '{' ||
str[i] == '[' ||
str[i] == '(') {
this->push(str[i]);
} else
if (this->top != NULL) {
if ((str[i] == '}' &&
this->top->data == '{') ||
(str[i] == ']' &&
this->top->data == '[') ||
(str[i] == ')' &&
this->top->data == '(')) {
//Remove a stack element
this->pop();
} else {
//If in case parentheses are not Balanced
status = false;
}
} else {
status = false;
}
}
if (status == true &&
this->top == NULL) {
cout << "\nBalanced\n";
} else {
cout << "\nNot Balanced\n";
}
//In case stack are not empty
//Then remove its elements
while (this->top != NULL) {
this->pop();
}
}
};
int main() {
MyStack obj =  MyStack();
string str = "[()]{}{[()()]()}";
cout << str;
obj.parentheses(str, str.size());
str = "(())[](){}{}[{]}";
cout << str;
obj.parentheses(str, str.size());
return 0;
}```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````/*
C# Program
Check Balanced parentheses using Stack
*/
//Stack Node
using System;
public class Node {
public char data;
public Node next;
public Node(char data) {
this.data = data;
next = null;
}
}
public class MyStack {
public Node top;
public MyStack() {
top = null;
}
//Add a new element in stack
public void push(char data) {
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null) {
new_node.next = top;
top = new_node;
} else {
Console.Write("Memory overflow\n");
}
}
//Add a top element in stack
public void pop() {
if (top != null) {
top = top.next;
}
}
public void parentheses(String str, int size) {
Boolean status = true;
for (int i = 0; i < size &&
status == true; ++i) {
if (str[i] == '{' ||
str[i] == '[' ||
str[i] == '(') {
push(str[i]);
} else
if (top != null) {
if ((str[i] == '}' &&
top.data == '{') ||
(str[i] == ']' &&
top.data == '[') ||
(str[i] == ')' &&
top.data == '(')) {
pop();
} else {
//If in case parentheses are not Balanced
status = false;
}
} else {
status = false;
}
}
if (status == true &&
top == null) {
Console.Write("\nBalanced\n");
} else {
Console.Write("\nNot Balanced\n");
}
//In case stack are not empty
//Then remove its elements
while (top != null) {
pop();
}
}
public static void Main(String[] args) {
MyStack obj = new MyStack();
String str = "[()]{}{[()()]()}";
Console.Write(str);
obj.parentheses(str, str.Length);
str = "(())[](){}{}[{]}";
Console.Write(str);
obj.parentheses(str, str.Length);
}
}```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````<?php
/*
Php Program
Check Balanced parentheses using Stack
*/
//Stack Node
class Node {
public \$data;
public \$next;

function __construct(\$data) {
\$this->data = \$data;
\$this->next = null;
}
}
class MyStack {
public \$top;

function __construct() {
\$this->top = null;
}
//Add a new element in stack

public 	function push(\$data) {
//Make a new stack node
\$new_node = new Node(\$data);
if (\$new_node != null) {
\$new_node->next = \$this->top;
\$this->top = \$new_node;
} else {
echo("Memory overflow\n");
}
}
//Add a top element in stack

public 	function pop() {
if (\$this->top != null) {
\$this->top = \$this->top->next;
}
}
public 	function parentheses(\$str, \$size) {
\$status = true;
for (\$i = 0; \$i < \$size &&
\$status == true; ++\$i) {
if (\$str[\$i] == '{' ||
\$str[\$i] == '[' ||
\$str[\$i] == '(') {
\$this->push(\$str[\$i]);
} else
if (\$this->top != null) {
if ((\$str[\$i] == '}' &&
\$this->top->data == '{') ||
(\$str[\$i] == ']' &&
\$this->top->data == '[') ||
(\$str[\$i] == ')' &&
\$this->top->data == '(')) {
//Remove a stack element
\$this->pop();
} else {
//If in case parentheses are not Balanced
\$status = false;
}
} else {
\$status = false;
}
}
if (\$status == true &&
\$this->top == null) {
echo("\nBalanced\n");
} else {
echo("\nNot Balanced\n");
}
//In case stack are not empty
//Then remove its elements
while (\$this->top != null) {
\$this->pop();
}
}
}

function main() {
\$obj = new MyStack();
\$str = "[()]{}{[()()]()}";
echo(\$str);
\$obj->parentheses(\$str,
strlen(\$str));
\$str = "(())[](){}{}[{]}";
echo(\$str);
\$obj->parentheses(\$str,
strlen(\$str));

}
main();```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````/*
Node Js Program
Check Balanced parentheses using Stack
*/
//Stack Node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyStack {
constructor() {
this.top = null;
}

//Add a new element in stack
push(data) {
//Make a new stack node
var new_node = new Node(data);
if (new_node != null) {
new_node.next = this.top;
this.top = new_node;
} else {
process.stdout.write("Memory overflow\n");
}
}

//Add a top element in stack
pop() {
if (this.top != null) {
this.top = this.top.next;
}
}
parentheses(str, size) {
var status = true;
for (var i = 0; i < size &&
status == true; ++i) {
if (str[i] == '{' ||
str[i] == '[' ||
str[i] == '(') {
this.push(str[i]);
} else
if (this.top != null) {
if ((str[i] == '}' &&
this.top.data == '{') ||
(str[i] == ']' &&
this.top.data == '[') ||
(str[i] == ')' &&
this.top.data == '(')) {
//Remove a stack element
this.pop();
} else {
//If in case parentheses are not Balanced
status = false;
}
} else {
status = false;
}
}

if (status == true &&
this.top == null) {
process.stdout.write("\nBalanced\n");
} else {
process.stdout.write("\nNot Balanced\n");
}

//In case stack are not empty
//Then remove its elements
while (this.top != null) {
this.pop();
}
}
}

function main(args) {
var obj = new MyStack();
var str = "[()]{}{[()()]()}";
process.stdout.write(str);
obj.parentheses(str, str.length);
str = "(())[](){}{}[{]}";
process.stdout.write(str);
obj.parentheses(str, str.length);
}

main();```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````#   Python 3 Program
#   Check Balanced parentheses using Stack

# Stack Node
class Node :

def __init__(self, data) :
self.data = data
self.next = None

class MyStack :

def __init__(self) :
self.top = None

# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = Node(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")

# Add a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next

def parentheses(self, str, size) :
status = True
i = 0
while (i < size and status == True) :
if (str[i] == '{'
or str[i] == '['
or str[i] == '(') :
self.push(str[i])
elif (self.top != None) :
if ((str[i] == '}' and self.top.data == '{')
or(str[i] == ']' and self.top.data == '[')
or(str[i] == ')' and self.top.data == '(')) :
# Remove a stack element
self.pop()
else :
# If in case parentheses are not Balanced
status = False

else :
status = False

i += 1

if (status == True and self.top == None) :
print("\nBalanced\n", end = "")
else :
print("\nNot Balanced\n", end = "")

# In case stack are not empty
# Then remove its elements
while (self.top != None) :
self.pop()

def main() :
obj = MyStack()
str = "[()]{}{[()()]()}"
print(str, end = "")
obj.parentheses(str, len(str))
str = "(())[](){}{}[{]}"
print(str, end = "")
obj.parentheses(str, len(str))

if __name__ == "__main__":
main()```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````#   Ruby Program
#   Check Balanced parentheses using Stack

# Stack Node
class Node
# Define the accessor and reader of class Node
attr_accessor :data, :next
def initialize(data)
self.data = data
@next = nil
end
end

class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top

def initialize()
@top = nil
end
# Add a new element in stack
def push(data)
# Make a new stack node
new_node = Node.new(data)
if (new_node != nil)
new_node.next = @top
@top = new_node
else
print("Memory overflow\n")
end
end
# Add a top element in stack
def pop()
if (@top != nil)
@top = @top.next
end
end
def parentheses(str, size)
status = true
i = 0
while (i < size &&
status == true)
if (str[i] == '{' ||
str[i] == '[' ||
str[i] == '(')
self.push(str[i])
elsif (@top != nil)
if ((str[i] == '}' &&
@top.data == '{') ||
(str[i] == ']' &&
@top.data == '[') ||
(str[i] == ')' &&
@top.data == '('))
# Remove a stack element
self.pop()
else
# If in case parentheses are not Balanced
status = false
end
else
status = false
end
i += 1
end
if (status == true &&
@top == nil)
print("\nBalanced\n")
else
print("\nNot Balanced\n")
end
# In case stack are not empty
# Then remove its elements
while (@top != nil)
self.pop()
end
end
end
def main()
obj = MyStack.new()
str = "[()]{}{[()()]()}"
print(str)
obj.parentheses(str, str.length())
str = "(())[](){}{}[{]}"
print(str)
obj.parentheses(str, str.length())
end

main()```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced
``````
``````/*
Scala Program
Check Balanced parentheses using Stack
*/
//Stack Node
class Node(var next: Node,
var data: Char) {

def this(data: Character) {
this( null,data);
}
}
class MyStack(var top: Node) {

def this() {
this(null);
}
//Add a new element in stack
def push(data: Character): Unit = {
//Make a new stack node
val new_node: Node = new Node(data);

if (new_node != null) {
new_node.next = this.top;
this.top = new_node;
} else {
print("Memory overflow\n");
}
}
//Add a top element in stack
def pop(): Unit = {
if (this.top != null) {
this.top = this.top.next;
}
}
def parentheses(str: String, size: Int): Unit = {
var status: Boolean = true;
var i: Int = 0;
while (i < size &&
status == true) {
if (str(i) == '{' ||
str(i) == '[' ||
str(i) == '(') {
this.push(str(i));
} else
if (this.top != null) {
if ((str(i) == '}' &&
this.top.data == '{') ||
(str(i) == ']' &&
this.top.data == '[') ||
(str(i) == ')' &&
this.top.data == '(')) {
//Remove a stack element
this.pop();
} else {
//If in case parentheses are not Balanced
status = false;
}
} else {
status = false;
}
i += 1;
}
if (status == true &&
this.top == null) {
print("\nBalanced\n");
} else {
print("\nNot Balanced\n");
}
//In case stack are not empty
//Then remove its elements
while (this.top != null) {
this.pop();
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyStack = new MyStack();
var str: String = "[()]{}{[()()]()}";
print(str);
obj.parentheses(str, str.length());
str = "(())[](){}{}[{]}";
print(str);
obj.parentheses(str, str.length());
}
}```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````
``````/*
Swift Program
Check Balanced parentheses using Stack
*/
//Stack Node
class Node {
var data: Character;
var next: Node? ;
init(_ data: Character) {
self.data = data;
next = nil;
}
}

class MyStack {
var top: Node? ;
init() {
top = nil;
}

//Add a new element in stack
func push(_ data: Character) {
//Make a new stack node
let new_node : Node? = Node(data);
if (new_node != nil) {
new_node!.next = top;
top = new_node;
} else {
print("Memory overflow\n", terminator: "");
}
}
//Add a top element in stack
func pop() {
if (top != nil) {
top = top!.next;
}
}
func parentheses(_ info: String , _ size : Int) {
var status = true;
var i = 0;

let str = Array(info);
while (i < size &&
status == true) {
if (str[i] == "{" ||
str[i] == "[" ||
str[i] == "(") {
self.push(str[i]);
} else
if (top != nil) {
if ((str[i] == "}" &&
top!.data == "{") ||
(str[i] == "]" &&
top!.data == "[") ||
(str[i] == ")" &&
top!.data == "(")) {
//Remove a stack element
self.pop();
} else {
//If in case parentheses are not Balanced
status = false;
}
} else {
status = false;
}
i += 1;
}
if (status == true &&
top == nil) {
print("\nBalanced\n", terminator: "");
} else {
print("\nNot Balanced\n", terminator: "");
}
//In case stack are not empty
//Then remove its elements
while (top != nil) {
self.pop();
}
}
}
func main() {
let obj = MyStack();
var str = "[()]{}{[()()]()}";
print(str, terminator: "");
obj.parentheses(str, str.count);
str = "(())[](){}{}[{]}";
print(str, terminator: "");
obj.parentheses(str, str.count);
}
main();```
```

#### Output

``````[()]{}{[()()]()}
Balanced
(())[](){}{}[{]}
Not Balanced``````

## Time Complexity Analysis

1. The `push` operation has a time complexity of O(1) as we simply add a character to the top of the stack.
2. The `pop` operation has a time complexity of O(1) as we simply remove a character from the top of the stack.
3. The `parentheses` function traverses the string once, and each character operation takes O(1) time. Hence, the time complexity for the `parentheses` function is O(n), where n is the size of the input string.

## Output Explanation

The output shows whether the given strings of parentheses are balanced or not. For example, for the input string "[()]{}{()()}", the output is "Balanced," indicating that the parentheses are balanced. For the input string "(()){}{}[{]}", the output is "Not Balanced," indicating that the parentheses are not balanced.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post