class Solution {
public:
    bool isValid(string s) {
		string left_parentheses(s.length()/2,'0');
		int i = 0, j = 0;
		while (s[i]) {
			if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
				left_parentheses[j] = s[i];
				j++;
			}
			else if ((s[i] == ')' && left_parentheses[j - 1] == '(')
				     || (s[i] == ']' && left_parentheses[j - 1] == '[')
				     || (s[i] == '}' && left_parentheses[j - 1] == '{')) {
				j--;
			}
			else {
				return false;
			}
			i++;
		}
		if(j == 0) return true;
		return false;
	}
};