首页 > > 程序设计 > C/C++ >

Leetcode 20 有效的括号valid-parentheses（…

2018-09-18 06:25:16来源：博客园阅读 ()

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

=============================================================
基本思路其实还是比较简单的， 我刚刚开始想得就十分的复杂。。。
首先分析一下：

左括号必须有右括号匹配，并且与其匹配的括号是同类型的；
不同类型的括号不能穿插含括，如例4，存在线性规则。

毫无疑问要使用栈了（虽然我看到了栈的标签了ehahaha...）

由上面的特性就可以得到基本思路：

碰到左括号则压入栈中；

碰到右括号，则与栈顶进行匹配，如果属于同类型，则把栈顶弹出（注意监测空栈），如果不同，return false；

最后监测空栈，不是空栈（有括号剩余），return false；

是空栈，return ture；

下面是AC代码：

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack <char> mark;
 5         for(char temp :s){
 6             if (temp=='(')
 7                 mark.push(')');
 8             else if(temp=='[')
 9                 mark.push(']');
10             else if(temp=='{')
11                 mark.push('}');
12             else{
13                 if (mark.empty()||temp!=mark.top())
14                     return false;      
15                 else mark.pop();
16             }
17         }
18         return mark.empty();
19         }              
20 };