# 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
{
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)
{
// Test
}
}``````

#### 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
{
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()
{
// Test
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
{
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)
{
// Test
}
}``````

#### 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
{
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()
{
// Test
}
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
{
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()
{
// Test
}
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 :
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() :
#  Test

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

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()
#  Test
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
{
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
}
}``````

#### 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
{
record.push(text[i]);
}
i += 1;
}
if (record.isEmpty() && result == true)
{
print(" Valid parentheses ", data);
}
else
{
print(" Not a Valid parentheses ", data);
}
}
}
func main()
{
// Test
}
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
{
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
{
// Test
}``````

#### 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 {
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.

## 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.