leetcode:20有效的括号——stack

思路分析

题目匹配的情况有两中：(){}[]和（[{}]）,匹配成功的思路是每个]或者其他右包围结构都是和最近的[或者其他左包围结构匹配.
“最近”匹配的思想应该使用stack结构对数据进行操作

代码框架

1.遍历整个string

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

2.对于灭一个元素，有两类性质：被判断的属性和判断的属性，被判断的元素应该存入stack，判断的元素应该作为局部变量
2.1遍历每一个元素：stack存入判断元素（被判别的属性）

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

2.2遍历每一个元素：（判别属性）

char c = stack.top();//取stack顶元素
 stack.pop();//取出stack顶元素

 char match;//判别元素代表的局部变量
 if( s[i] == ')' )
     match = '(';
 else if( s[i] == ']' )
     match = '[';
 else{
     assert( s[i] == '}' );//断言函数，表示必定是},或者也可以用if函数 if(s[i]=='}')
     match = '{';
 }

 if(c != match)
     return false;

整体代码

class Solution {
public:
    bool isValid(string s) {

        stack<char> stack;
        for( int i = 0 ; i < s.size() ; i ++ ){
            if( s[i] == '(' || s[i] == '{' || s[i] == '[')
                stack.push(s[i]);
            else{

                if( stack.size() == 0 )
                    return false;

                char c = stack.top();
                stack.pop();

                char match;
                if( s[i] == ')' )
                    match = '(';
                else if( s[i] == ']' )
                    match = '[';
                else{
                    if(s[i]=='}')
 
                    match = '{';
                }

                if(c != match)
                    return false;
            }
        }
        if( stack.size() != 0 )
            return false;//奇数个元素，返回false

        return true;//和for同层，在判别完所有元素返回
    }
};