2-8 符号配对 (20分)-HBU DS

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

输入格式:

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

输出格式:

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

输入样例1：

void test() { int i, A[10]; for (i=0; i<10; i++) /*/ A[i] = i; } .

输出样例1：

NO /*-?

输入样例2：

void test() { int i, A[10]; for (i=0; i<10; i++) /**/ A[i] = i; }] .

输出样例2：

NO ?-]

输入样例3：

void test() { int i double A[10]; for (i=0; i<10; i++) /**/ A[i] = 0.1*i; } .

输出样例3：

YES

思路

总体思路：如果是那四对符号就入栈，如果是右半部分符号，恰能与栈顶的符号匹配，就把匹配的左符号pop（当然，右符号也不用push）

因为堆栈的操作都是用int写的，而且我感觉前面都是单字符和/*俩字符有点小乱，就把他们转换成了数字。1 2 3 4 -1 -2 -3 -4分别对应 ( [ { / * ) ] } */ 。

首先是存下字符串。大家可能知道 while(cin>>num)…这种用法，其实getline()函数也一样，遇到无效输入或者EOF时，也会使他的条件为假，终止输入。但是getline()虽然接受了\n但不存储\n,所以每句后面加个\n。

然后判断，是否是那四对字符（串）。如果是作符号，就直接入栈，如果是右符号，首先有两种情况，一种是栈还是空，第一个不匹配的就是缺少左符号，如果不是空，那还有两种情况，一种是此符号与栈顶元素不匹配，第一个不匹配的就是此时栈顶的左符号缺少对应的右括号；如果匹配，栈顶元素出栈。遇到一个不匹配的直接break了。

**注意：**有一种情况是 ：开头有多余左括号（测试点3），所以记得如果最后栈不为空，也是不匹配。

踩的坑

我就是测试点3一直过不去，找了一中午bug，然后下课的时候问班里的一个大佬总有一个点过不去怎么办，她说这个题（也有别的好多题）可以去pta的固定习题集-浙江DS习题集里看看，里面测试点都用说明。于是我一看，呼~原来如此！原来是这种情况。

#include <iostream> #include <string> using namespace std; typedef struct Node *Stack; struct Node { int data; Stack next; }; Stack CreatStack(); bool isEmpty(Stack S); void Push(Stack S, int x); int Pop(Stack S); int topItem(Stack S); int main() { Stack S = CreatStack(); string str, temp; int error = 0; int end = 0; while (getline(cin, temp)) str += (temp + '\n'); for (auto it = str.begin(); it != str.end(); it++) { int top = 0; if (!isEmpty(S)) { top = topItem(S); } int num = 0; if (*it == '(') num = 1; else if (*it == '[') num = 2; else if (*it == '{') num = 3; else if (*it == ')') num = -1; else if (*it == ']') num = -2; else if (*it == '}') num = -3; else if (*it == '/' && (it + 1) != str.end() && *(it + 1) == '*') { num = 4; it++; } else if (*it == '*' && (it + 1) != str.end() && *(it + 1) == '/') { num = -4; it++; } else if ((*it == '.' && (it + 1) != str.end() && *(it + 1) == '\n')) { end = 1; break; } if (num > 0) //如果是左边符号直接push Push(S, num); else if (num < 0) //如果是右边符号 { if (top == 0) //如果前面没有了，那么就是缺少左括号 { error = num; } else { if (top + num) //如果当前符号与栈末符号不匹配，那么出错的就是左括号 { error = top; break; } else Pop(S); } } if (end) break; } //没有错误，但是栈不为空 的情况，即有多余左括号，这时的第一个不匹配符号应该在栈末 if (error == 0 && !isEmpty(S)) { while (!isEmpty(S)) error = Pop(S); } if (error == 0) { cout << "YES"; } else { cout << "NO" << endl; if (error < 0) { cout << "?-"; if (error == -1) cout << ')'; else if (error == -2) cout << ']'; else if (error == -3) cout << '}'; else cout << "*/"; } else { if (error == 1) cout << '('; else if (error == 2) cout << '['; else if (error == 3) cout << '{'; else cout << "/*"; cout << "-?"; } } } Stack CreatStack() { Stack S = (Stack)malloc(sizeof(Node)); S->next = NULL; return S; } bool isEmpty(Stack S) { if (S->next) return false; else return true; } void Push(Stack S, int x) { Stack currNode = (Stack)malloc(sizeof(Node)); currNode->data = x; currNode->next = S->next; S->next = currNode; } int topItem(Stack S) { if (isEmpty(S)) { return 0; } int temp; temp = S->next->data; return temp; } int Pop(Stack S) { if (isEmpty(S)) { return 0; } int temp; Stack del = S->next; temp = S->next->data; S->next = S->next->next; free(del); return temp; }