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

括号匹配：

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

对于输入的括号序列，建议使用标准的 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;
	else
		return 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;
	else
		cout << "匹配失败" << 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;
    else
        return 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;
    else
        return false;

}

int main() {
    string str;
        cin >> str;// 使用标准的 C++ 字符串
        if (Matching(str))
            cout << "匹配成功" << endl;
        else
            cout << "匹配失败" << 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);
        // 如果出栈的字符与字符串后半部分的字符不相等，说明不是回文，返回 false
        if (ch != st[strlen(st) - 1 - (S.top - S.base)])
            return false;
  }

    // 如果栈为空且没有找到不相等的字符，说明是回文，返回 true
    return true;
}
int main() {
    char st[100];
    // 使用 cin.getline 输入字符串
    cin.getline(st, 100);
    bool b = huiwen(st);
    if (b)
        cout << "是回文" << endl;
    else
        cout << "不是回文" << endl;
    return 0;

}