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

AC代码

#include <iostream>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

bool isValid(string s)
{
    	stack<char> lefts;
    	for(int i = 0; i < s.size(); ++i)
    	{
    		char c = s[i];
    		if(c == '(' || c == '[' || c == '{')
    			lefts.push(c);
    		else
    		{
    			if(lefts.size() == 0)
    				return false;
    			char top = lefts.top();
    			if(c == ')')
    			{
    				if(top != '(')
    					return false;
    			}
    			else if(c == ']')
    			{
    				if(top != '[')
    					return false;
    			}
    			else if(c == '}')
    			{
    				if(top != '{')
    					return false;
    			}
    			lefts.pop();
    		}
    	}
    	return lefts.size() == 0;
}

int main()
{
    	string s;
    
    #ifndef ok
    	freopen("in3.in", "r", stdin);
    	freopen("std3.out","w", stdout);
    #endif
    
    	while(cin>>s)
    	{
    		if(isValid(s))
    			cout<<"true"<<endl;
    		else
    			cout<<"false"<<endl;
    	}
    
    #ifndef ok
    	fclose(stdin);
    	fclose(stdout);
    #endif
    
    	return 0;
}