数据结构—栈操作经典案例

括号匹配：

这是我最开始写的，运行有问题

对于输入的括号序列，建议使用标准的 C++ 字符串而不是字符数组。

#include<iostream> 
using namespace std;typedef char SelemType;
typedef int Status;
#define OK 1
#define MAXSIZE 100
#define ERROR -1// 定义栈结构
typedef struct {SelemType* base;SelemType* top;int stacksize;
} sqstack;// 初始化栈
Status InitStack(sqstack& S) {S.base = new SelemType[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;return OK;
}// 入栈操作
Status Push(sqstack& S, SelemType e) {if (S.top - S.base == S.stacksize)return ERROR;*S.top++ = e;return OK;
}// 出栈操作
Status Pop(sqstack& S, SelemType& e) {if (S.top == S.base)return ERROR;e = *--S.top;return OK;
}//判断栈空
bool StackEmpty(sqstack S) {if (S.top == S.base)return true;elsereturn false;
}//取栈顶元素
SelemType Gettop(sqstack S) {if (!StackEmpty)return *(S.top - 1);
}//括号匹配 
bool Macthing(SelemType a[]) {sqstack S;InitStack(S);SelemType e;int flag = 1;for (int i = 1; i <= strlen(a); i++) {while (flag && a[i] != '\0') {switch (a[i]) {case '[':case'(':Push(S, a[i]);case']':if (!StackEmpty && Gettop(S) == '[')Pop(S, e);else{flag = 0;break;}case')':if (!StackEmpty && Gettop(S) == '(')Pop(S, e);else{flag = 0;break;}}}}if (StackEmpty(S) && flag) return true;else return false;}int main() {SelemType a[] = { "(([]))" };if (Macthing(a))cout << "匹配成功" << endl;elsecout << "匹配失败" << endl;}

修改如下


使用标准的 C++ 字符串string str = "(([]))"; 
bool Matching(string a) ；while (flag && i < a.length())

完整代码：

#include<iostream> 
using namespace std;typedef char SelemType;
typedef int Status;
#define OK 1
#define MAXSIZE 100
#define ERROR -1// 定义栈结构
typedef struct {SelemType* base;SelemType* top;int stacksize;
}SqStack;// 初始化栈
Status InitStack(SqStack& S) {S.base = new SelemType[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;return OK;
}// 入栈操作
Status Push(SqStack& S, SelemType e) {if (S.top - S.base == S.stacksize)return ERROR; *S.top++ = e;return OK;
}// 出栈操作
Status Pop(SqStack& S, SelemType& e) {if (S.top == S.base)return ERROR; e = *--S.top;return OK;
}// 判断栈是否为空
bool IsStackEmpty(SqStack S) { if (S.top == S.base)return true;elsereturn false;
}// 获取栈顶元素
SelemType GetTop(SqStack S) {return *(S.top-1);
}// 括号匹配 
bool Matching(string a) {SqStack S;InitStack(S);SelemType e;int i = 0;bool flag = true;while (flag && i < a.length()) {switch (a[i]) {case '[':case '(':Push(S, a[i]);break; case ']':if (!IsStackEmpty(S) && GetTop(S) == '[')Pop(S, e);else {flag = false;break; }break; case ')':if (!IsStackEmpty(S) && GetTop(S) == '(')Pop(S, e);else {flag = false;break; }break; }i++;}if (IsStackEmpty(S) && flag)return true;elsereturn false;}int main() {string str;cin >> str;// 使用标准的 C++ 字符串if (Matching(str))cout << "匹配成功" << endl;elsecout << "匹配失败" << endl;return 0;}

运行结果：

基本栈操作和前面一致，后面不再给出。

进制转化

代码：


//进制转化void converse(int N, int d) {
sqstack S;
InitStack(S);
while (N) {
SelemType ch;
int k = N % d;
ch = k <= 9 ? '0' + k : 'A' + k - 10;
Push(S, ch);
N = N/ d;
}
SelemType h; //h接收弹出栈的元素
while (S.top != S.base) {
Pop(S, h);
cout << h;
}
}
int main() {
cout << "12分别转化为2进制，8进制，16进制" << endl;
Conversion(12, 2);
cout << endl;
Conversion(12, 8);
cout << endl;
Conversion(12, 16);
}

运行结果：

回文判断：

代码：

//判断是否回文bool huiwen(char st[]) {sqstack S;InitStack(S);// 遍历字符串的前半部分并入栈for (int i = 0; i < strlen(st) / 2; i++) {Push(S, st[i]); }SelemType ch;// 当栈不为空时，继续出栈比较while (S.top != S.base) {Pop(S, ch);// 如果出栈的字符与字符串后半部分的字符不相等，说明不是回文，返回 falseif (ch != st[strlen(st) - 1 - (S.top - S.base)])return false;}// 如果栈为空且没有找到不相等的字符，说明是回文，返回 truereturn true;
}
int main() {char st[100];// 使用 cin.getline 输入字符串cin.getline(st, 100);bool b = huiwen(st);if (b)cout << "是回文" << endl;elsecout << "不是回文" << endl;return 0;}