Given a string containing just the characters '(' ')' '{' '}' '[' ']'
,
and
, determine if the input string is valid.
The brackets must close in the correct order,
"()"
"()[]{}"
are all valid but "(]"
"([)]"
are not.
括号比對的問題,使用棧解決。(注意,通路棧元素時要先判斷棧是否為空)
C++實作代碼如下:
#include<iostream>
#include<string>
#include<stack>
using namespace std;
class Solution {
public:
bool isValid(string s) {
size_t index=0;
stack<char> ss;
while(index<s.length())
{
char c;
switch(s[index])
{
case '(' :
case '[' :
case '{' :
ss.push(s[index]);
break;
case ')' :
if(ss.empty())
return false;
c=ss.top();
if(c!='(')
return false;
ss.pop();
break;
case ']' :
if(ss.empty())
return false;
c=ss.top();
if(c!='[')
return false;
ss.pop();
break;
case '}' :
if(ss.empty())
return false;
c=ss.top();
if(c!='{')
return false;
ss.pop();
break;
default:
return false;
}
index++;
}
if(index==s.length()&&ss.empty())
return true;
return false;
}
};
int main()
{
string str="]";
Solution s;
cout<<s.isValid(str)<<endl;
}
#include<string>
#include<iostream>
#include<stack>
using namespace std;
class Solution
{
public:
bool isValid(string s)
{
stack<char> st;
int i;
for(i=0;i<(int)s.size();i++)
{
switch(s[i])
{
case '(':
case '[':
case '{':
st.push(s[i]);
break;
case ')':
if(st.empty()||st.top()!='(')
return false;
st.pop();
break;
case ']':
if(st.empty()||st.top()!='[')
return false;
st.pop();
break;
case '}':
if(st.empty()||st.top()!='{')
return false;
st.pop();
break;
}
}
if(st.empty())
return true;
else
return false;
}
};
int main()
{
Solution s;
string str="((()))";
cout<<s.isValid(str)<<endl;
}