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

20. Правильная скобочная запись

Задана строка, состоящая только из символов '(', ')', '{', '}', '[' и ']'. Определите, является ли строка правильной.

Скобки должны закрываться в правильном порядке: "()" и "()[]{}" корректны, а "(]" и "([)]" не являются правильными.

// C++

class Solution {

public:

bool isValid(string s) {

}

};

// Java

public class Solution {

public boolean isValid(String s) {

}

}

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Для решения задачи будем использовать символьный стек. Будем двигаться последовательно по символам входной строки и:

· если текущий символ является открывающейся скобкой, то заносим его в стек.

· если текущий символ является закрывающейся скобкой, то на вершине стека должна находиться соответствующая ему открывающаяся скобка. Если это не так, или если стек пуст, то скобочное выражение не является правильным.

По окончанию обработки правильной строки стек должен оказаться пустым.

Реализация алгоритма

class Solution

{

public:

bool isValid(string s)

{

stack<char> st;

for(int i = 0; i < s.size(); i++)

{

if ((s[i] == '(') || (s[i] == '[') || (s[i] == '{')) st.push(s[i]);

else

{

if (st.empty()) return false;

if ((s[i] == ')') && (st.top() != '(')) return false;

if ((s[i] == ']') && (st.top() != '[')) return false;

if ((s[i] == '}') && (st.top() != '{')) return false;

st.pop();

}

}

return st.empty();

}

};

Java реализация

public class Solution

{

public boolean isValid(String s)

{

Stack<Character> st = new Stack<Character>();

for(int i = 0; i < s.length(); i++)

{

if ((s.charAt(i) == '(') || (s.charAt(i) == '[') || (s.charAt(i) == '{'))

st.push(s.charAt(i));

else

{

if (st.empty()) return false;

if ((s.charAt(i) == ')') && (st.peek() != '(')) return false;

if ((s.charAt(i) == ']') && (st.peek() != '[')) return false;

if ((s.charAt(i) == '}') && (st.peek() != '{')) return false;

st.pop();

}

}

return st.empty();

}

}