当前位置: 代码迷 >> 综合 >> 深入理解数据结构——堆栈应用(括号匹配)
  详细解决方案

深入理解数据结构——堆栈应用(括号匹配)

热度:31   发布时间:2024-01-17 05:10:32.0
#include <iostream>
#include <string>using namespace std;typedef char Etype;//顺序存储堆栈
struct Stack {Etype* element;int top;int maxsize;
};//创建空堆栈
void CreateStack(Stack& S, int MaxStackSize) {S.maxsize = MaxStackSize;S.element = new Etype[S.maxsize];//创建数组元素S.top = -1;//top指向的是数据空间的第一个元素,本身的值代表数据元素的下表,空表设top为-1
}//判断堆栈是否为空
bool IsEmpty(Stack& S) {if (S.top == -1) return true;else return false;
}//判断堆栈是否满了
bool IsFull(Stack& S) {if (S.top >= S.maxsize - 1) return true;else return false;
}//返回栈顶元素的值
bool GetTop(Stack& S, Etype& result) {if (IsEmpty(S)) return false;result = S.element[S.top];return true;
}//出栈操作,将栈顶元素取出,并且将top指向下一个元素的位置
bool Pop(Stack& S, Etype& result) {if (IsEmpty(S)) return false;result = S.element[S.top];S.top--;//栈顶指向下一个元素地址return true;
}//进栈操作,将top+1,输入元素存入新的栈顶
bool Push(Stack& S, Etype& x) {//传入的是x的地址if (IsEmpty(S)) return false;S.top++;S.element[S.top] = x;return true;
}//检验表达式中的括号匹配
//匹配“{()()}}#”
void Matching(char exp[]) {//传入一个字符串数组char ch;int MaxStackSize = 10;Stack S;CreateStack(S, MaxStackSize);ch = *exp++;while (ch != '#') {switch (ch) {case '(': {Push(S, ch); break;}case '[': {Push(S, ch); break;}case ')': {if (!IsEmpty(S)) {Pop(S, ch);if (ch != '(')//return ;cout << "error11:右边是),左边不是(!"<<endl;}else//return ;cout << "error12:右边是],左边没有任何括号!" << endl;break;}case ']': {if (!IsEmpty(S)) {Pop(S, ch);if (ch != '[')//return ;cout << "error21:右边是],左边不是[!" << endl;}else//return ;cout << "error22:右边是],左边没有任何括号!" << endl;break;}}ch = *exp++;}if(!IsEmpty(S))//returncout << "error3:右边括号,左边没有括号了!" << endl;
}