题目:Valid Parentheses
题目来源:leetcode
题目描述:
Given a string containing just the characters
'('
,
')'
,
'{'
,
'}'
,
'['
and
']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order
解题思路:
- 建立一个string的栈
- 指针指向字符串(下标)
- 与栈顶的字符比较,若栈为空直接压入栈,如和栈顶匹配,则将栈顶弹出,若未匹配,括号直接压入栈中
- 指针向后移一位,回到3,直到字符串被扫描完
- 如栈为空,则括号匹配为真,反则为假
全部代码:
1 class Solution {
2 public:
3 bool isValid(string s) {
4 bool match(char,char);
5 stack<char> stk;
6 for(int i=0;i<s.size();++i)
7 {
8 if(stk.size()==0) stk.push(s[i]);
9 else
10 {
11 if(match(stk.top(),s[i])) stk.pop();
12 else stk.push(s[i]);
13 }
14 }
15 if(stk.size()==0) return true;
16 else return false;
17 }
18 };
19 bool match(char f,char l)
20 {
21 switch(f)
22 {
23 case '(': if(l==')') return true;break;
24 case '[': if(l==']') return true;break;
25 case '{': if(l=='}') return true;break;
26 }
27 return false;
28 }
转载于:https://www.cnblogs.com/cuphoria/p/9605774.html