[刷题] 20 Valid Parentheses

要求

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合
空字符串可被认为是有效字符串

思路

遇到左方向括号入栈，遇到右方向括号查看栈顶元素，匹配则出栈
遍历结束后栈为空则满足匹配原则

实现

 1 #include<iostream>

 2 #include<stack>

 3 #include<cassert>

 4

 5 using namespace std;

 6

 7 class Solution{

 8     public:

 9         bool isValid(string s){

10

11             stack<char> stack;

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

13                 if( s[i] == '(' || s[i] == '{' || s[i] == '[')

14                     stack.push( s[i] );

15                 else{

16

17                     if( stack.size() == 0)

18                         return false;

19

20                     char c = stack.top();

21                     stack.pop();

22

23                     char match;

24                     if( s[i] == ')')

25                         match = '(';

26                     else if( s[i] == ']' )

27                         match = '[';

28                     else{

29                         assert( s[i] == '}' );

30                         match = '{';

31                     }

32

33                     if( c != match)

34                         return false;

35                 }

36             }

37

38             if( stack.size() != 0 )

39                 return false;

40

41             return true;

42         }

43 };

44

45 void printBool(bool res){

46     cout << (res ? "True" : "False") << endl;

47 }

48

49 int main(){

50

51     printBool(Solution().isValid("()"));

52     printBool(Solution().isValid("()[]{}"));

53     printBool(Solution().isValid("(]"));

54     printBool(Solution().isValid("([)]"));

55

56     return 0;

57 }

巴特西

[刷题] 20 Valid Parentheses

最新文章

热门文章