[C++]利用棧實作字元串裡的括号比對

題目：Valid Parentheses

題目來源：leetcode

題目描述：

Given a string containing just the characters

'('

,

')'

,

'{'

,

'}'

,

'['

and

']'

, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order

 解題思路：

1. 建立一個string的棧
2. 指針指向字元串（下标）
3. 與棧頂的字元比較，若棧為空直接壓入棧，如和棧頂比對，則将棧頂彈出，若未比對，括号直接壓入棧中
4. 指針向後移一位，回到3，直到字元串被掃描完
5. 如棧為空，則括号比對為真，反則為假

全部代碼：

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