Skip to main content

Check valid parentheses using stack

The problem is to check whether a given expression containing parentheses is valid or not using a stack. A valid expression should have properly matched pairs of open and close parentheses. Each open parenthesis must have a corresponding close parenthesis, and the order of opening and closing should be correct. For example, "()", "(()())", and "(())" are valid expressions, but ")(", "(()" are not.

Problem Statement

Given a string containing only parentheses (open and close), we need to determine whether the expression is valid or not using a stack.

Example

Consider the following examples:

  1. Input: "(()())"

    • Stack: (empty)
    • Add '(' to the stack.
    • Add '(' to the stack.
    • Add ')' and pop '(' from the stack.
    • Add ')' and pop '(' from the stack.
    • Add '(' to the stack.
    • Add ')' and pop '(' from the stack.
    • Add ')' and pop '(' from the stack.
    • Stack: (empty)
    • Result: Valid expression.

  2. Input: ")("

    • Stack: (empty)
    • Add ')' to the stack.
    • Stack: ')'
    • Add '(' to the stack.
    • Stack: ')('
    • Result: Not a valid expression.

Idea to Solve the Problem

To check if the given expression containing parentheses is valid or not, we can use a stack to keep track of the opening parentheses. We iterate through the expression from left to right. For each character, if it is an opening parenthesis '(', we push it into the stack. If it is a closing parenthesis ')', we check if the stack is empty or not. If the stack is empty, it means there is no corresponding opening parenthesis, and the expression is invalid. If the stack is not empty, we pop the top element from the stack, which represents the last unmatched opening parenthesis. If the character is not a parenthesis, we ignore it and continue to the next character.

After iterating through the entire expression, if the stack is empty, it means all the opening parentheses have been properly matched with closing parentheses, and the expression is valid. Otherwise, the expression is invalid.

Pseudocode

Function isValidParentheses(text):
    Create an empty stack called record
    Set i to 0
    Set n to the length of text
    Set result to true
    While i is less than n and result is true:
        If text[i] is ')':
            If record is empty:
                Set result to false
            Else:
                Set auxiliary to record.peek()
                If auxiliary is equal to '(':
                    Pop from record
                Else:
                    Set result to false
        Else:
            Push text[i] into record
        Increment i by 1
    If record is empty and result is true:
        Display "Valid parentheses " + text
    Else:
        Display "Not a Valid parentheses " + text

Algorithm

  1. Create a class called ValidExpression.
  2. Define a function called isValidParentheses which takes the input string text.
  3. Create an empty stack called record to store opening parentheses.
  4. Initialize a variable i to 0 to keep track of the current character index in the string.
  5. Initialize a variable n to the length of the input string text.
  6. Initialize a boolean variable result to true to keep track of whether the expression is valid or not.
  7. Iterate through the input string text using a while loop until i is less than n and result is true: a. If the current character at index i in the string is ')':
    • If the stack record is empty, it means there is no corresponding opening parenthesis, so set result to false.
    • If the stack record is not empty, get the top element from the stack and check if it is '('.
      • If it is '(', it means the closing parenthesis matches the last unmatched opening parenthesis, so pop the top element from the stack to remove it.
      • If it is not '(', it means there is a mismatch in parentheses, so set result to false. b. If the current character at index i in the string is '(', it means it is an opening parenthesis, so push it into the stack record. c. Increment the value of i by 1 to move to the next character in the string.
  8. After the while loop, check if the stack record is empty and result is true:
    • If the stack is empty, it means all the opening parentheses have been properly matched with closing parentheses, and the expression is valid.
    • If the stack is not empty, it means there are unmatched opening parentheses, and the expression is invalid.
  9. Display the appropriate message based on the result.

Code Solution

import java.util.Stack;
/*
    Java program for
    Check valid parentheses using stack
*/
public class ValidExpression
{
	public void isValidParentheses(String text)
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		Stack < Character > record = new Stack < Character > ();
		int i = 0;
		int n = text.length();
		boolean result = true;
		char auxiliary;
		while (i < n && result)
		{
			if (text.charAt(i) == ')')
			{
				if (record.isEmpty())
				{
					result = false;
				}
				else
				{
					auxiliary = record.peek();
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.pop();
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text.charAt(i));
			}
			i++;
		}
		if (record.isEmpty() && result == true)
		{
			System.out.println(" Valid parentheses " + text);
		}
		else
		{
			System.out.println(" Not a Valid parentheses " + text);
		}
	}
	public static void main(String[] args)
	{
		ValidExpression task = new ValidExpression();
		// Test
		task.isValidParentheses("()()()");
		task.isValidParentheses("((())");
		task.isValidParentheses("((())())");
		task.isValidParentheses("((())))");
	}
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
    C++ program for
    Check valid parentheses using stack
*/
class ValidExpression
{
	public: void isValidParentheses(string text)
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		stack < char > record;
		int i = 0;
		int n = text.length();
		bool result = true;
		char auxiliary;
		while (i < n && result)
		{
			if (text[i] == ')')
			{
				if (record.size() == 0)
				{
					result = false;
				}
				else
				{
					auxiliary = record.top();
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.pop();
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text[i]);
			}
			i++;
		}
		if (record.size() == 0 && result == true)
		{
			cout << " Valid parentheses " << text << endl;
		}
		else
		{
			cout << " Not a Valid parentheses " << text << endl;
		}
	}
};
int main()
{
	ValidExpression *task = new ValidExpression();
	// Test
	task->isValidParentheses("()()()");
	task->isValidParentheses("((())");
	task->isValidParentheses("((())())");
	task->isValidParentheses("((())))");
	return 0;
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Check valid parentheses using stack
*/
public class ValidExpression
{
	public void isValidParentheses(String text)
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		Stack < char > record = new Stack < char > ();
		int i = 0;
		int n = text.Length;
		Boolean result = true;
		char auxiliary;
		while (i < n && result)
		{
			if (text[i] == ')')
			{
				if ((record.Count == 0))
				{
					result = false;
				}
				else
				{
					auxiliary = record.Peek();
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.Pop();
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.Push(text[i]);
			}
			i++;
		}
		if ((record.Count == 0) && result == true)
		{
			Console.WriteLine(" Valid parentheses " + text);
		}
		else
		{
			Console.WriteLine(" Not a Valid parentheses " + text);
		}
	}
	public static void Main(String[] args)
	{
		ValidExpression task = new ValidExpression();
		// Test
		task.isValidParentheses("()()()");
		task.isValidParentheses("((())");
		task.isValidParentheses("((())())");
		task.isValidParentheses("((())))");
	}
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
<?php
/*
    Php program for
    Check valid parentheses using stack
*/
class ValidExpression
{
	public	function isValidParentheses($text)
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		$record = array();
		$i = 0;
		$n = strlen($text);
		$result = true;
		$auxiliary;
		while ($i < $n && $result)
		{
			if ($text[$i] == ')')
			{
				if (empty($record))
				{
					$result = false;
				}
				else
				{
					$auxiliary = end($record);
					if ($auxiliary == '(')
					{
						// When valid pair of open and close
						array_pop($record);
					}
					else
					{
						// mismatch parentheses pair
						$result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				array_push($record, $text[$i]);
			}
			$i++;
		}
		if (empty($record) && $result == true)
		{
			echo(" Valid parentheses ".$text."\n");
		}
		else
		{
			echo(" Not a Valid parentheses ".$text."\n");
		}
	}
}

function main()
{
	$task = new ValidExpression();
	// Test
	$task->isValidParentheses("()()()");
	$task->isValidParentheses("((())");
	$task->isValidParentheses("((())())");
	$task->isValidParentheses("((())))");
}
main();

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
/*
    Node JS program for
    Check valid parentheses using stack
*/
class ValidExpression
{
	isValidParentheses(text)
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		var record = [];
		var i = 0;
		var n = text.length;
		var result = true;
		var auxiliary = ' ';
		while (i < n && result)
		{
			if (text.charAt(i) == ')')
			{
				if ((record.length == 0))
				{
					result = false;
				}
				else
				{
					auxiliary = record[record.length - 1];
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.pop();
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text.charAt(i));
			}
			i++;
		}
		if ((record.length == 0) && result == true)
		{
			console.log(" Valid parentheses " + text);
		}
		else
		{
			console.log(" Not a Valid parentheses " + text);
		}
	}
}

function main()
{
	var task = new ValidExpression();
	// Test
	task.isValidParentheses("()()()");
	task.isValidParentheses("((())");
	task.isValidParentheses("((())())");
	task.isValidParentheses("((())))");
}
main();

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
#    Python 3 program for
#    Check valid parentheses using stack
class ValidExpression :
	def isValidParentheses(self, text) :
		#  Per Request text which is contains 
		#  open and close parentheses
		#  Use to collect parentheses characters
		record = []
		i = 0
		n = len(text)
		result = True
		auxiliary = ' '
		while (i < n and result) :
			if (text[i] == ')') :
				if ((len(record) == 0)) :
					result = False
				else :
					auxiliary = record[-1]
					if (auxiliary == '(') :
						#  When valid pair of open and close
						record.pop()
					else :
						#  mismatch parentheses pair
						result = False
					
				
			else :
				#  Add open parentheses
				record.append(text[i])
			
			i += 1
		
		if ((len(record) == 0) and result == True) :
			print(" Valid parentheses ", text)
		else :
			print(" Not a Valid parentheses ", text)
		
	

def main() :
	task = ValidExpression()
	#  Test
	task.isValidParentheses("()()()")
	task.isValidParentheses("((())")
	task.isValidParentheses("((())())")
	task.isValidParentheses("((())))")

if __name__ == "__main__": main()

Output

 Valid parentheses  ()()()
 Not a Valid parentheses  ((())
 Valid parentheses  ((())())
 Not a Valid parentheses  ((())))
#    Ruby program for
#    Check valid parentheses using stack
class ValidExpression 
	def isValidParentheses(text) 
		#  Per Request text which is contains 
		#  open and close parentheses
		#  Use to collect parentheses characters
		record = []
		i = 0
		n = text.length
		result = true
		auxiliary = ' '
		while (i < n && result) 
			if (text[i] == ')') 
				if ((record.length == 0)) 
					result = false
				else
 
					auxiliary = record.last
					if (auxiliary == '(') 
						#  When valid pair of open and close
						record.pop()
					else
 
						#  mismatch parentheses pair
						result = false
					end

				end

			else
 
				#  Add open parentheses
				record.push(text[i])
			end

			i += 1
		end

		if ((record.length == 0) && result == true) 
			print(" Valid parentheses ", text, "\n")
		else
 
			print(" Not a Valid parentheses ", text, "\n")
		end

	end

end

def main() 
	task = ValidExpression.new()
	#  Test
	task.isValidParentheses("()()()")
	task.isValidParentheses("((())")
	task.isValidParentheses("((())())")
	task.isValidParentheses("((())))")
end

main()

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))

import scala.collection.mutable._;
/*
    Scala program for
    Check valid parentheses using stack
*/
class ValidExpression()
{
	def isValidParentheses(text: String): Unit = {
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		var record: Stack[Character] = new Stack[Character]();
		var i: Int = 0;
		var n: Int = text.length();
		var result: Boolean = true;
		var auxiliary: Char = ' ';
		while (i < n && result)
		{
			if (text.charAt(i) == ')')
			{
				if (record.isEmpty)
				{
					result = false;
				}
				else
				{
					auxiliary = record.top;
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.pop;
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text.charAt(i));
			}
			i += 1;
		}
		if (record.isEmpty && result == true)
		{
			println(" Valid parentheses " + text);
		}
		else
		{
			println(" Not a Valid parentheses " + text);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: ValidExpression = new ValidExpression();
		// Test
		task.isValidParentheses("()()()");
		task.isValidParentheses("((())");
		task.isValidParentheses("((())())");
		task.isValidParentheses("((())))");
	}
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
import Foundation;
/*
    Swift 4 program for
    Check valid parentheses using stack
*/
struct Stack
{
	private
	var items: [Character] = []
	func peek()->Character
	{
		if (self.isEmpty()==false)
		{
			return items.first!
		}
		else
		{
			fatalError("This stack is empty.")
		}
	}
	func isEmpty()->Bool
	{
		return items.count == 0
	}
	mutating func pop()->Character
	{
		return items.removeFirst()
	}
	mutating func push(_ data: Character)
	{
		items.insert(data, at: 0)
	}
}
class ValidExpression
{
	func isValidParentheses(_ data: String)
	{
      	let text = Array(data);
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		var record = Stack();
		var i: Int = 0;
		let n: Int = text.count;
		var result: Bool = true;
		var auxiliary: Character = " ";
		while (i < n && result)
		{
			if (text[i] == ")")
			{
				if (record.isEmpty())
				{
					result = false;
				}
				else
				{
					auxiliary = record.pop();
					if (auxiliary != "(")
					{
						
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text[i]);
			}
			i += 1;
		}
		if (record.isEmpty() && result == true)
		{
			print(" Valid parentheses ", data);
		}
		else
		{
			print(" Not a Valid parentheses ", data);
		}
	}
}
func main()
{
	let task: ValidExpression = ValidExpression();
	// Test
	task.isValidParentheses("()()()");
	task.isValidParentheses("((())");
	task.isValidParentheses("((())())");
	task.isValidParentheses("((())))");
}
main();

Output

 Valid parentheses  ()()()
 Not a Valid parentheses  ((())
 Valid parentheses  ((())())
 Not a Valid parentheses  ((())))
import java.util.Stack;
/*
    Kotlin program for
    Check valid parentheses using stack
*/
class ValidExpression
{
	fun isValidParentheses(text: String): Unit
	{
		// Per Request text which is contains 
		// open and close parentheses
		// Use to collect parentheses characters
		val record: Stack < Char > = Stack < Char > ();
		var i: Int = 0;
		val n: Int = text.length;
		var result: Boolean = true;
		var auxiliary: Char ;
		while (i < n && result)
		{
			if (text.get(i) == ')')
			{
				if (record.empty())
				{
					result = false;
				}
				else
				{
					auxiliary = record.peek();
					if (auxiliary == '(')
					{
						// When valid pair of open and close
						record.pop();
					}
					else
					{
						// mismatch parentheses pair
						result = false;
					}
				}
			}
			else
			{
				// Add open parentheses
				record.push(text.get(i));
			}
			i += 1;
		}
		if (record.empty() && result == true)
		{
			println(" Valid parentheses " + text);
		}
		else
		{
			println(" Not a Valid parentheses " + text);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: ValidExpression = ValidExpression();
	// Test
	task.isValidParentheses("()()()");
	task.isValidParentheses("((())");
	task.isValidParentheses("((())())");
	task.isValidParentheses("((())))");
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))
package main
import "fmt"
/*
    Go program for
    Check valid parentheses using stack
*/

func isValidParentheses(text string) {
	// Per Request text which is contains 
	// open and close parentheses
	// Use to collect parentheses characters
	var record = make([]byte,0)
	var i int = 0
	var n int = len(text)
	var result bool = true
	var auxiliary byte = ' '
	for (i < n && result) {
		if text[i] == ')' {
			if len(record) == 0 {
				result = false
			} else {
				auxiliary = record[len(record) - 1]
				if auxiliary == '(' {
					// When valid pair of open and close
					record = record[:len(record) - 1]
				} else {
					// mismatch parentheses pair
					result = false
				}
			}
		} else {
			// Add open parentheses
			record = append(record, text[i])
		}
		i++
	}
	if len(record) == 0 && result == true {
		fmt.Println(" Valid parentheses ", text)
	} else {
		fmt.Println(" Not a Valid parentheses ", text)
	}
}
func main() {
	
	// Test
	isValidParentheses("()()()")
	isValidParentheses("((())")
	isValidParentheses("((())())")
	isValidParentheses("((())))")
}

Output

 Valid parentheses ()()()
 Not a Valid parentheses ((())
 Valid parentheses ((())())
 Not a Valid parentheses ((())))

Time Complexity

The time complexity of the isValidParentheses function is O(n), where n is the length of the input string text. This is because we need to iterate through the entire string once to check the validity of parentheses.

Explanation

  • For the first example "()"()(), all the parentheses have been properly matched, so the expression is valid.
  • For the second example "((())", there is one unmatched opening parenthesis, so the expression is invalid.
  • For the third example "((())())", all the parentheses have been properly matched, so the expression is valid.
  • For the fourth example "((())))", there are two unmatched opening parentheses, so the expression is invalid.
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