leetcode No20. Valid Parentheses

本文主要是介绍leetcode No20. Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++中栈(stack)的用法

s.empty()               //如果栈为空返回true，否则返回false  
s.size()                //返回栈中元素的个数  
s.pop()                 //删除栈顶元素但不返回其值  
s.top()                 //返回栈顶的元素，但不删除该元素  
s.push()                //在栈顶压入新元素

Question:

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.

大意是判断括号是否合法

Algorithm：

左括号为(、{、[

右括号为)、}、]

假设我们消去一对紧邻并且匹配的左右括号，就不会影响全局的匹配判断，而且能有效的把问题简化。

用栈来解决这个问题，顺序遍历字符串，如果遇到左括号就进栈，遇到右括号则判断栈顶的括号和当前遍历到的括号是否匹配，如果不匹配则非法，如果匹配则出栈。循环结束后，如果栈是空的则合法。

一开始我想到可以用计数器来计数匹配情况，但是当括号种类大于一种时，例如[(])两个计数器都会复位为零，但是它却不匹配。用栈可以便捷地推广至多种括号并存的情况。

Accepted Code：

class Solution {
public:bool isValid(string s) {stack<char> res;for(int i=0;i<s.size();i++){if(s[i]=='('||s[i]=='{'||s[i]=='[')res.push(s[i]);else if(s[i]==')'||s[i]=='}'||s[i]==']'){if(res.empty()==1)return false;if((res.top()=='('&&s[i]==')')||(res.top()=='{'&&s[i]=='}')||(res.top()=='['&&s[i]==']'))res.pop();else return false;}}return res.empty();}
};