# Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

The following is my code, which has already been tested on a onlinejudge. Can someone help me give some comments for the code itself?

bool isValid(string s) {
stack<char> s1;
string::iterator it = s.begin();
map<char, char> x;
x['('] = ')';
x['['] = ']';
x['{'] = '}';

for (; it!=s.end(); ++it) {
if (!s1.empty()) {
char c = s1.top();
if(x[c] == *it) {
s1.pop();
}
else {
s1.push(*it);
}
}
else {
s1.push(*it);
}
}

return s1.empty();
}

• Instead of a stack you could use recursion. – rightfold Mar 21 '13 at 18:45
• It seems your code validates ())))) as correct? T. – konijn Mar 21 '13 at 18:53

You use of objects without prefix them with std:: is a bad sign.
I bet you used using namespace std; in the code. Please stop this habit.
https://stackoverflow.com/q/1452721/14065

When passing objects to functions prefer to pass by const reference to prevent unnecessary copies.

bool isValid(std::string const& s) {
//      ^^^^^       ^^^^^^


To prevent you accidentally modifying things try and use cost_itrerator when you need only read only accesses to a container:

 std::string::const_iterator it = s.begin();


In C++11 you can use the new 'brace init' feature:

map<char, char> x;
x['('] = ')';
x['['] = ']';
x['{'] = '}';

//replace with:
map<char, char> x = {{'(', ')'}, {'[',']'},{'{','}'}};


Also because this is a imutable you can make it const and static. The const will help prevent errors while the static is so you only create it once.

static map<char, char> const x = {{'(', ')'}, {'[',']'},{'{','}'}};


Loki’s answer is good but I agree with Zoidberg’s comment and would completely reformulate this as a recursion. That way you can solve the problem in a more declarative way.

The upshot: your code reads more like a formulation of the problem rather than a bunch of technical stuff, and is thus potentially easier to understand, although in this simple case the explicit stack is just fine.

The idea of the algorithm can be summarised as follows:

• a string is correctly nested if it is empty; or
• a string is correctly nested if
• the next character is an expected group closing character and
• the subsequent string is correctly nested; or
• a string is correctly nested if
• the next character is a group opening character and
• the subsequent string is correct and closes the group and
• the subsequent string after that is correctly nested.

It makes sense to reformulate this slightly so that we first test whether the next character is expected (either an “end” character if no group is open, or an expected group closing character). If that isn’t the case we assume that a group is being opened and proceed accordingly.

This can be translated line for line into C++:

match valid_group(char const* str, char expected = '\0') {
if (*str == expected)
return {true, str + 1};

if (*str == '\0')
return false;

match result = valid_group(str + 1, closing_char(*str));

if (not result.valid)
return result;

return valid_group(result.pos, expected);
}


Here match is a type that holds whether the validation so far is successful, and at which position to resume validation; I’ve merely added an implicit constructor that allows us to write return false; rather than return {false, str};:

struct match {
bool valid;
char const* pos;

match(bool valid, char const* pos = nullptr) : valid(valid), pos(pos) {}
};


Oh yeah, and closing_char does just that:

char closing_char(char c) {
switch (c) {
case '(': return ')';
case '[': return ']';
case '{': return '}';
default: return 'X';
}
}


… so obviously this function assumes that the input only contains valid braces and no other characters; in particular, valid_group("}X"); would return true.