栈:
- 满足先进后出的特性
- 若是左括号,尝试加入栈顶
- 若是右括号,尝试匹配
#include <iostream>
#include <stack>
using namespace std;
bool left(char c)//检查左括号
{
return c == '(' || c == '[' || c == '{';
}
bool right(char c)//检查右括号
{
return c == '(' || c == ']' || c == '}';
}
bool check(char a, char b)//检查栈顶
{
return a == b;
}
bool match(string s)
{
stack<char> p;
for (int i = 0; i <s.size(); i ++ )
if (left(s[i]))
p.push(s[i]);
else if (right(s[i]))
{
if (!p.empty() || check(p.top(), s[i]))//栈不空,且匹配正确
{
p.pop();
}
else return false;//匹配失败,返回false
}
if (!p.empty()) return false;//栈不空,说明存在没有匹配的左括号,返回false
return true;//全部匹配成功
}