The expression is allowed to contain both parentheses and square brackets, and the nesting order of these brackets can be arbitrary.
For example: "( [ ] ( ) )" and "[ ( [ ] [ ] ) ]" are both correctly matched, while "[ ( ] )" and "( ( ) ) )" are incorrectly matched.
The task here is to check whether the parentheses in a given expression are correctly matched.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
Input a string S consisting only of parentheses and square brackets. The length of S does not exceed 500 characters. | If the parentheses in the expression are correctly matched, output "Right"; otherwise, output "Wrong". |
[([][])] | Right |
[(]) | Wrong |
Thought Process
Run a For loop over the string. If it is a left parenthesis, store this character in a Vector. If it is a right parenthesis, check if the last character in the Vector matches this right parenthesis. If they match, pop_back the last data in the Vector. If they don't match, output "Wrong" directly and break the loop. If there is still data in the Vector after the For loop, output "Wrong".
Sample Code-ZeroJudge K621: How to Pair Brackets?
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
vector<char>v;
bool ok = true;
for (int i = 0; i<str.length(); i++)
{
if (str[i] == '(' || str[i] == '[')
{
v.push_back(str[i]);
}
else
{
if (str[i] == ')')
{
if (v.size() > 0 && v[int(v.size()-1)] == '(') v.pop_back();
else
{
ok = false;
cout << "Wrong\n";
break;
}
}
else
{
if (v.size() > 0 && v[int(v.size()-1)] == '[') v.pop_back();
else
{
ok = false;
cout << "Wrong\n";
break;
}
}
}
}
if (ok && v.size() != 0)
{
ok = false;
cout << "Wrong\n";
}
if (ok) cout << "Right\n";
}
//ZeroJudge K621
//Dr. SeanXD