H : 括号匹配
Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 76 Solved: 31
Description
给一个长度不大于100的字符串，问该字符串里出现的括号是否合法。
字符串只会出现三种括号，“[]”，“()”，“{}”，且形如“({[]})”为合法，形如“[(])”为不合法。
Input
单组数据。
长度不大于100的字符串，字符串中不存在空格。
Output
如果该字符串中出现的所有括号都合法，输出“Yes”，否则输出“No”。
Sample Input
(a+b)!=c
Sample Output
Yes
Hint
一、题目大意
用字符匹配。由于字符匹配有一个先来后匹配的特点。
实际考查栈操作。包括：入栈，出栈，读取栈顶，判断栈是否为空四种操作。
二、思路
栈特点：先入后出
1、储备知识
| 函数 | 功能 | 例子 |
|---|---|---|
| push() | 入栈 | stack< int>sta;sta.push(5),sta.push(2),sta.push(0);//即往栈中插入5,2,0 |
| pop() | 出栈 | sta.pop();//弹出栈顶，此时栈中只剩5,2 |
| top() | 获取栈顶值 | 此时sta.top()==2 |
| empty() | 判断栈是否为空 | 此时empty()=0。当又执行两次sta.pop()弹出的时候，栈空了，此时empty()=1 |
注1：头文件：#include
注2:pop()弹出的时候，要保证栈不为空
2、思路A
就硬模拟栈
遇到（，[,{就入栈。
遇到），]，}就开始判断，如果栈空了就No
否则，栈也弹出一个判断是否匹配，不匹配->No
循环完，如果栈还有字符-》No
不是No就是Yes
#include<iostream>
#include<stack>
using namespace std;
int main()
{
string ch;
while(cin>>ch)
{
int flag=1;
stack<char>sta;
for(int i=0;i<ch.size();i++)
{
if(ch[i]=='('||ch[i]=='['||ch[i]=='{')sta.push(ch[i]);//如果遇到（，[,{就加入栈
if(ch[i]==')'||ch[i]==']'||ch[i]=='}') //遇到),],}就出栈然后比较是否符号符合题意即可
{
if(sta.empty()){flag=0;break;} //中途空了这肯定No
char c=sta.top();
sta.pop();
if(c=='('&&ch[i]!=')'||c=='['&&ch[i]!=']'||c=='{'&&ch[i]!='}'){flag=0;break;}//没匹配对，No
}
}
if(!sta.empty())flag=0; //字符串结束，却栈中还有匹配完的字符,也No
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
