完成以下程序，并在右边空白处，对错误进行修改，并记录下程序运行结果：

 

1. 编写算法，判断一表达式中的括号是否配对，包括大、中、小三类括号。

链表版本：

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <stack> #include <string> using namespace std; /**栈的链式存储**/ typedef struct Data{ char c; }; typedef struct Stack{ Data data; Stack *top; //指向栈顶元素 }; /**初始化空栈**/ void InitStack(Stack *S){ S->top = NULL; } /**判断是否为空栈**/ int StackEmpty(Stack S){ //为空返回1否则返回0 if(S.top==NULL) return 1; else return 0; } /**返回栈顶元素**/ void GetTop(Stack S,Data *d){ if(StackEmpty(S)==1) printf("It's an empty stack!"); else{ d->c = S.top->data.c; } } /**向栈顶插入新元素 入栈**/ void PushStack(Stack *S,Data d){ Stack* p = (Stack *)malloc(sizeof(Stack)); p->data.c = d.c; p->top = S->top; S->top = p; } /**从栈顶删除元素 出栈**/ void PopStack(Stack *S,Data *d){ if(StackEmpty(*S)==1){ printf("It's an empty stack!\n"); }else{ Stack *p = S->top; S->top = p->top; d->c = p->data.c; } } /**清空栈**/ void ClearStack(Stack *S){ if(StackEmpty(*S)==1){ printf("It's already an empty stack!\n"); }else{ S->top = NULL; } } /**打印栈内信息**/ void PrintStack(Stack S){ if(StackEmpty(S)==1){ printf("It's an empty stack!\n"); }else{ printf("name----age\n"); while(S.top!=NULL){ printf("%s\n",S.top->data.c); S.top = S.top->top; } } } /**检查右括号与栈顶元素是否匹配**/ int Match(Data r,Data s){ //匹配成功返回1 if(r.c==')'&&s.c=='('){ return 1; }else if(r.c=='}'&&s.c=='{'){ return 1; }else if(r.c==']'&&s.c=='['){ return 1; }else{ return 0; } } /**括号匹配**/ int CheckMatch(char *m,Stack *S){ Data r,s; while(*m){ switch (*m){ case '(': case '{': case '[': s.c = *m; //赋值 PushStack(S,s); //进栈 *m++; //向后移动 break; case ')': case '}': case ']': if(StackEmpty(*S)){ //栈空 printf("数据中 %s 没有匹配!\n",*m); return 0; } GetTop(*S,&s); //获取栈顶元素 r.c = *m; if(Match(r,s)){ //匹配判断 PopStack(S,&s); *m++; }else{ printf("数据中 %c 没有匹配项!\n",*m); return 0; } default: *m++; } } return 1; } int main(){ char d[100]; Stack S; //定义一个S的栈 char *p; //定义一个指针 scanf("%s", d); p = d; //指向表达式 InitStack(&S); //初始换栈 if(CheckMatch(p,&S)) { printf("匹配成功！\n"); } //匹配栈 else printf("匹配不成功！"); return 0; }

 

 

C++版本：

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <stack> #include <string> using namespace std; typedef long long LL; char a[100]; int n, m; stack <char> s; int main() { scanf("%s", a+1); int len = strlen(a + 1); int flag = 1; int f = 0; cout << "len == " << len << endl; while(len) { len--; // cout << "now == " << a[flag] << endl; if(a[flag] == '{' || a[flag] == '[' || a[flag] == '(') { s.push(a[flag]); flag++; } else if( flag == 1 && (a[flag] == '}' || a[flag] == ']' || a[flag] == ')')) { f = 1; break; } else if((a[flag] == '}' && s.top() == '{') || (a[flag] == ']' && s.top() == '[')|| (a[flag] == ')' && s.top() == '(') ){ s.pop(); flag++; continue; } else{ cout << "a[flag] == " << a[flag] << endl; cout << "s.top == " << s.top() << endl; f = 1; break; } } if(f == 1) cout << "这个括号没有完全匹配" << endl; else cout << "括号已经完全匹配" << endl; return 0; }