I have to write a testing program for parenthesis. For example, the brackets mus
ID: 3741226 • Letter: I
Question
I have to write a testing program for parenthesis. For example, the brackets must close in the correct order, "()" and "()[]{}" are all valid but "([])" is not.
Here is my program.
bool isValid(string s)
{
stack<char> parenthesis;
for (int i = 0; i < s.size(); i++)
{
if(s[i] == '(' || s[i] == '[' || s[i] == '{' )
parenthesis.push(s[i]);
else
{
if(parenthesis.empty())
return false;
if(s[i] == ')' && parenthesis.top() != '(')
return false;
if(s[i] == ']' && parenthesis.top() != '[')
return false;
if(s[i] == '}' && parenthesis.top() != '{')
return false;
parenthesis.pop();
}
}
return parenthesis.empty();
}
Here is the main program:
int main()
{
string s;
cout << "Input string" << endl;
cin >> s;
if(isValid(s))
cout << "Valid" << endl;
else
cout << "Invalid" << endl;
return 0;
}
Explanation / Answer
#include<iostream>
#include<stack>
using namespace std;
/*****
I have changed the isValid Function as the paranthesis match has to be like (), (){}[] like if any opening bracket is there then there must be immediate correspondign
closing bracket.
So impletemnt this first the length of the string must be even
then all the brackets at position 0, 2, 4 ... it must be opening brackets. Push them to the stack
Now iterate thorough from end of the string .Last bracket must be corresponding to the top of the stack
By following above algorithm if we reach to the end then its a valid bracket else in valid
******/
bool isValid(string s)
{
stack<char> parenthesis;
if(s.size() %2 != 0){
return false;
}
for (int i = 0; i < s.size(); i = i+2)
{
if(s[i] != '(' && s[i] != '[' && s[i] != '{' ){
return false;
}
else
parenthesis.push(s[i]);
}
for(int j = s.size()-1; j>0; j = j-2){
char toMatch = s[j];
if(s[j] == ')' && parenthesis.top() != '('){
return false;
}else if(s[j] == ']' && parenthesis.top() != '['){
return false;
}else if(s[j] == '}' && parenthesis.top() != '{'){
return false;
}
parenthesis.pop();
}
return parenthesis.empty();
}
int main()
{
string s;
cout << "Input string" << endl;
cin >> s;
if(isValid(s))
cout << "Valid" << endl;
else
cout << "Invalid" << endl;
return 0;
}