首页 > 其他 > 详细

[Leetcode] valid parentheses 有效括号对

时间:2017-07-16 11:50:52      阅读:219      评论:0      收藏:0      [点我收藏+]

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.

 题意:给定字符串判断是否为合法的括号对

思路:利用栈结构,遇到左括号((、[、{)都压入栈中,遇到右括号了,若栈为空,则肯定不合法;若栈不为空,则看其是否和栈顶字符向匹配。这里以最后栈是否为空来判断整个字符串是否合法,不然类似于((( [ ] )),就会合法的了。代码如下:

 1 class Solution {
 2 public:
 3     bool isValid(string s) 
 4     {
 5         if(s.empty())   return true;
 6         stack<char> stk;
 7         for(int i=0;i<s.size();++i)
 8         {
 9             if(s[i]==(||s[i]==[||s[i]=={)
10                 stk.push(s[i]);
11             else 
12             {
13                 if( stk.empty())
14                     return false;
15                  char temp=stk.top();
16                  stk.pop();
17                  if((temp==(&&s[i] !=))||(temp==[&&s[i] !=])||(temp=={&&s[i] !=}))
18                      return false;
19             }
20             
21         }
22         return stk.empty();    
23     }
24 };

 

括号的题还有generate parentheses 

[Leetcode] valid parentheses 有效括号对

原文:http://www.cnblogs.com/love-yh/p/7189871.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!