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]=='(')
    {
      //Add stack element
      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)=='(')
      {
        //Add stack element
        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] == '(') {
				//Add stack element
				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] == '(') {
				//Add stack element
				$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] == '(') {
				//Add stack element
				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] == '(') :
				# Add stack element
				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_reader :data, :next
    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_reader :top
    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] == '(') 
				 # Add stack element
				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) == '(') {
				//Add stack element
				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] == "(") {
				//Add stack element
				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.

New Comment







Relative Post