Skip to main content

Check Balanced parentheses using Stack

Here given code implementation process.

//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
Last updated on by Kalkicode




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