符号配对

题目链接

题目描述

请编写程序检查C语言程序中下列符号是否配对：/* 与 */,(与),[与],{与}

输入描述

输入为一个c语言程序的一部分。当读到某一行中只有一个句点“.”和一个回车时，标志着输入结束。程序中需要检查配对的符号不超过2000个。

输出描述

如果所有符号都配对正确，则在第一行输出YES。否则在第一行输出NO，然后再第二行指出第一个不配对的符号：如果缺少左符号，则输出“?-右符号”；如果缺少右符号，则输出“左符号-？”。

样例

输入
void test()
{
int i, A[10];
for (i=0; i<10; i++) /**/
A[i] = i;
}]
.
输出
NO
?-]

思路：

• 遇到左符号直接入栈
• 遇到右符号
  • 判断栈是否为空，若为空则找到第一个不匹配的符号，输出即可。
  • 否则判断其与栈顶符号是否匹配，若匹配则删除栈顶元素，继续扫描，否则找到了第一个不匹配的符号，即栈顶元素，退出循环。
• 扫描结束后，若栈为空，则所有符号匹配成功，否则栈顶元素为第一个不匹配的符号，输出即可

难点： /* 的处理，将其合并为一个字符，便于判断

---

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
string s;
stack<char> st;
map<char,char> mp;
void work() {mp[')'] = '(';mp[']'] = '[';mp['}'] = '{';
}
int main() {work();string tep;while(cin >> tep) {if(tep==".") break;s+=tep;}bool ok = 1;string res;for(int i=0; i<s.size(); i++) {if(s[i]=='(' || s[i]=='[' || s[i]=='{') st.push(s[i]);if(s[i]=='/' && i+1<s.size() && s[i+1]=='*') {st.push('x');i++;continue;}if(s[i]==')' || s[i]==']' || s[i]=='}') {if(st.empty()) {puts("NO");cout<<"?-"<<s[i];return 0;}if(mp[s[i]] == st.top()) st.pop();else ok = 0;}if(s[i]=='*' && i+1<s.size() && s[i+1]=='/') {if(st.empty()) {puts("NO");cout<<"?-"<<s[i]<<s[i+1];return 0;}i++;if(st.top()=='x') st.pop();else ok = 0;}if(!ok) break;}if(st.empty()) puts("YES");else {puts("NO");if(st.top()=='x') res = "/*";else res = st.top();cout<<res<<"-?";}return 0;
}