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:
-
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.
-
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
- Create a class called
ValidExpression
. - Define a function called
isValidParentheses
which takes the input stringtext
. - Create an empty stack called
record
to store opening parentheses. - Initialize a variable
i
to 0 to keep track of the current character index in the string. - Initialize a variable
n
to the length of the input stringtext
. - Initialize a boolean variable
result
to true to keep track of whether the expression is valid or not. - Iterate through the input string
text
using a while loop untili
is less thann
andresult
is true: a. If the current character at indexi
in the string is ')':- If the stack
record
is empty, it means there is no corresponding opening parenthesis, so setresult
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 indexi
in the string is '(', it means it is an opening parenthesis, so push it into the stackrecord
. c. Increment the value ofi
by 1 to move to the next character in the string.
- If the stack
- After the while loop, check if the stack
record
is empty andresult
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.
- 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.
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