題目描述
給定一個只包括 '('粥鞋，')'，'{'瞄崇，'}'呻粹，'['，']' 的字符串苏研，判斷字符串是否有效等浊。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合摹蘑。
注意空字符串可被認(rèn)為是有效字符串筹燕。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
思路
遇到左括號入棧
-
遇到右括號
- 與棧頂元素不匹配，return false
- 與棧頂元素匹配，棧頂元素出棧
掃描完畢撒踪，椆В空 return true, 棧不空 return false。
特殊情況：
椫仆空的時候遇到右括號掸绞，直接 false。
class Solution {
public:
bool isValid(string s) {
int i;
stack<char> st;
int length = s.length();
for(i = 0; i < length; i++)
{
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
{
st.push(s[i]);
}
else if(s[i] == ')' || s[i] == '}' || s[i] == ']')
{
if(!st.empty())
{
char stTop = st.top();
if( stTop == '(' && s[i] != ')' )
{
return false;
}
else if(stTop == '{' && s[i] != '}')
{
return false;
}
else if(stTop == '[' && s[i] != ']')
{
return false;
}
else
{
st.pop();
}
}
else
{
return false;
}
}
}
if(st.empty())
{
return true;
}
else
return false;
}
};
