学习目标：

学会栈，咋一看栈很怪异, 为啥要搞一个比顺序表更简单的结构? 知道它的一些应用之后才懂得其强大.

学习指导：帆神的代码

学习任务：

1. 抄写代码

2. 目录

   1定义结构体

   2操作方法

   2.1打印栈

    2.2初始化栈

   2.3入栈操作 

   2.4出栈操作 

   3测试

   3.1测试类

   3.2测试结果

   4全部代码

   5久违的bug

   5.1编译器报错找不到CharSrack

   5.2测试类报错

    5.3，我的打印结果有问题

   6两个练习题

   习题1 栈的应用 -- 括号匹配

   1括号匹配判断操作

   2测试类及测试结果

   3括号匹配全部代码

   4老师程序在我的编译器上运行的BUG：

    习题2 栈的应用 -- 表达式求值

   1全部代码

   ---

代码说明：

1.初始化为一个空栈. top 指向栈顶元素, 所以它的初始值为 − 1 -1−1.
2.push 的时候, 需要先改变 top 再放元素.
3.pop 的时候, 需要先改变 top 再 return.

学习时间：

2022.5.10

1定义结构体

typedef struct CharStack {
	int top;
	int data[STACK_MAX_SIZE];
} *CharStackPtr,CharStack;

2操作方法

2.1打印栈

void outputStack(CharStackPtr paraStack) {
	printf("栈内元素有:");
	for (int i = 0; i <= paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}
	printf("n");
}

 2.2初始化栈

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;
	return resultPtr;
}

2.3入栈操作 

void push(CharStackPtr paraStackPtr, int paraValue) {
	//1检查栈内是否还有空间
	if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
		printf("栈满，无法继续添加元素n");
		return;
	}
	//2移动栈顶
	paraStackPtr->top++;
	//3添加元素进栈
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

2.4出栈操作 

char pop(CharStackPtr paraStackPtr) {
	//1检查栈内是否有元素
	if (paraStackPtr->top < 0) {
		printf("栈空，无法取出元素n");
		return '';
	}
	//2移动栈顶
	paraStackPtr->top--;
	//3添加元素
	return paraStackPtr->data[paraStackPtr->top + 1];
}

3测试

3.1测试类

void pushPopTest() {
	printf("---- pushPopTest 测试开始 ----n");

	CharStackPtr tempStack = charStackInit();
	printf("初始化后栈是: n");
	outputStack(tempStack);
	char ch;

	for (ch = 'a'; ch < 'm'; ch ++) {
		printf("元素%c 入栈.n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}

	for (int i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("元素 %c出栈.n", ch);
		outputStack(tempStack);
	}

	printf("---- pushPopTest 测试结束 ----n");
}

3.2测试结果

---- pushPopTest 测试开始 ----
初始化后栈是:
栈内元素有:
元素a 入栈.
栈内元素有:a
元素b 入栈.
栈内元素有:a b
元素c 入栈.
栈内元素有:a b c
元素d 入栈.
栈内元素有:a b c d
元素e 入栈.
栈内元素有:a b c d e
元素f 入栈.
栈内元素有:a b c d e f
元素g 入栈.
栈内元素有:a b c d e f g
元素h 入栈.
栈内元素有:a b c d e f g h
元素i 入栈.
栈内元素有:a b c d e f g h i
元素j 入栈.
栈内元素有:a b c d e f g h i j
元素k 入栈.
栈满，无法继续添加元素
栈内元素有:a b c d e f g h i j
元素l 入栈.
栈满，无法继续添加元素
栈内元素有:a b c d e f g h i j
元素 j出栈.
栈内元素有:a b c d e f g h i
元素 i出栈.
栈内元素有:a b c d e f g h
元素 h出栈.
栈内元素有:a b c d e f g
---- pushPopTest 测试结束 ----

--------------------------------
Process exited after 0.0472 seconds with return value 31

Press ANY key to continue...

4全部代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack {
	int top;
	int data[STACK_MAX_SIZE];
} *CharStackPtr,CharStack;


void outputStack(CharStackPtr paraStack) {
	printf("栈内元素有:");
	for (int i = 0; i <= paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}
	printf("n");
}

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;
	return resultPtr;
}

void push(CharStackPtr paraStackPtr, int paraValue) {
	//1检查栈内是否还有空间
	if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
		printf("栈满，无法继续添加元素n");
		return;
	}
	//2移动栈顶
	paraStackPtr->top++;
	//3添加元素进栈
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

char pop(CharStackPtr paraStackPtr) {
	//1检查栈内是否有元素
	if (paraStackPtr->top < 0) {
		printf("栈空，无法取出元素n");
		return '';
	}
	//2移动栈顶
	paraStackPtr->top--;
	//3添加元素
	return paraStackPtr->data[paraStackPtr->top + 1];
}


void pushPopTest() {
	printf("---- pushPopTest 测试开始 ----n");

	CharStackPtr tempStack = charStackInit();
	printf("初始化后栈是: n");
	outputStack(tempStack);
	char ch;

	for (ch = 'a'; ch < 'm'; ch ++) {
		printf("元素%c 入栈.n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}

	for (int i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("元素 %c出栈.n", ch);
		outputStack(tempStack);
	}

	printf("---- pushPopTest 测试结束 ----n");
}

void main() {
	pushPopTest();
}

5久违的bug

5.1编译器报错找不到CharSrack

 于是在结构体的地方手动加了一个就不报错了

5.2测试类报错

由于老师的ch是在第一个for里面定义的，我的编译器在第二个for里面找不到，所以把ch定义在外面就解决了。

 5.3，我的打印结果有问题

写完之后打印出来的栈全是$$$，我还以为是我改的那两个小点出bug了，仔细一想好像又不太可能

---- pushPopTest 测试开始 ----
初始化后链表是:
元素a 入栈.
$
元素b 入栈.
$ $
元素c 入栈.
$ $ $
元素d 入栈.
$ $ $ $
元素e 入栈.
$ $ $ $ $
元素f 入栈.
$ $ $ $ $ $
元素g 入栈.
$ $ $ $ $ $ $
元素h 入栈.
$ $ $ $ $ $ $ $
元素i 入栈.
$ $ $ $ $ $ $ $ $
元素j 入栈.
$ $ $ $ $ $ $ $ $ $
元素k 入栈.
栈满，无法继续添加元素
$ $ $ $ $ $ $ $ $ $
元素l 入栈.
栈满，无法继续添加元素
$ $ $ $ $ $ $ $ $ $
元素 j出栈.
$ $ $ $ $ $ $ $ $
元素 i出栈.
$ $ $ $ $ $ $ $
元素 h出栈.
$ $ $ $ $ $ $
---- pushPopTest 测试结束 ----

--------------------------------
Process exited after 0.03805 seconds with return value 31

Press ANY key to continue...

 可能是太渴望$了，所以去要打印处找错，发现这个data后面[i]漏了，加上就好了

6两个练习题

习题1 栈的应用 -- 括号匹配

1括号匹配判断操作

bool bracketMatching(char* paraString, int paraLength) {
	//1通过在底部压入“#”来初始化栈。
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;

	//2操作paraString进行括号匹配
	for (int i = 0; i < paraLength; i++) {
		tempChar = paraString[i];
		//前括号入栈，后括号判断前括号并出栈
		switch (tempChar) {
			//前括号入栈
			case '(':
				push(tempStack, tempChar);
				break;
			case '[':
				push(tempStack, tempChar);
				break;
			case '{':
				push(tempStack, tempChar);
				break;
			//后括号判断是否与前括号匹配，并出栈
			case ')':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '(') {
					return false;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '[') {
					return false;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '{') {
					return false;
				}
				break;
			//非括号元素，不进行操作，返回继续操作下一个元素
			default:
				break;
		}
	}

	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return true;
	}

	return true;
}

2测试类及测试结果

2.1测试类

void bracketMatchingTest() {
	printf("---- bracketMatchingTest 测试开始 ----n");
	char *tempExpression = (char*)"[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);


	tempExpression = (char*)"( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);

	tempExpression = (char*)"()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);

	tempExpression = (char*)"({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);


	tempExpression = (char*)")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);
	printf("---- bracketMatchingTest 测试结束 ----n");
}

2.2测试结果

---- bracketMatchingTest 测试开始 ----
对于表达式 '[2 + (1 - 3)] * 4'
括号是否匹配? 1

对于表达式 '( )  )'
括号是否匹配? 0

对于表达式 '()()(())'
括号是否匹配? 1

对于表达式 '({}[])'
括号是否匹配? 1

对于表达式 ')('
括号是否匹配? 0

---- bracketMatchingTest 测试结束 ----

--------------------------------
Process exited after 0.0348 seconds with return value 0

Press ANY key to continue...

3括号匹配全部代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack {
	int top;
	int data[STACK_MAX_SIZE];
} *CharStackPtr, CharStack;


void outputStack(CharStackPtr paraStack) {
	printf("栈内元素有:");
	for (int i = 0; i <= paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}
	printf("n");
}

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;
	return resultPtr;
}

void push(CharStackPtr paraStackPtr, int paraValue) {
	//1检查栈内是否还有空间
	if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
		printf("栈满，无法继续添加元素n");
		return;
	}
	//2移动栈顶
	paraStackPtr->top++;
	//3添加元素进栈
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

char pop(CharStackPtr paraStackPtr) {
	//1检查栈内是否有元素
	if (paraStackPtr->top < 0) {
		printf("栈空，无法取出元素n");
		return '';
	}
	//2移动栈顶
	paraStackPtr->top--;
	//3添加元素
	return paraStackPtr->data[paraStackPtr->top + 1];
}


bool bracketMatching(char* paraString, int paraLength) {
	//1通过在底部压入“#”来初始化栈。
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;

	//2操作paraString进行括号匹配
	for (int i = 0; i < paraLength; i++) {
		tempChar = paraString[i];
		//前括号入栈，后括号判断前括号并出栈
		switch (tempChar) {
			//前括号入栈
			case '(':
				push(tempStack, tempChar);
				break;
			case '[':
				push(tempStack, tempChar);
				break;
			case '{':
				push(tempStack, tempChar);
				break;
			//后括号判断是否与前括号匹配，并出栈
			case ')':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '(') {
					return false;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '[') {
					return false;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '{') {
					return false;
				}
				break;
			//非括号元素，不进行操作，返回继续操作下一个元素
			default:
				break;
		}
	}

	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return true;
	}

	return true;
}


void bracketMatchingTest() {
	printf("---- bracketMatchingTest 测试开始 ----n");
	char *tempExpression = (char*)"[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);


	tempExpression = (char*)"( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);

	tempExpression = (char*)"()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);

	tempExpression = (char*)"({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);


	tempExpression = (char*)")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("对于表达式 '%s' n括号是否匹配? %d nn", tempExpression, tempMatch);
	printf("---- bracketMatchingTest 测试结束 ----n");
}


int main() {
	bracketMatchingTest();
	return 0;
}

4老师程序在我的编译器上运行的BUG：

抄完一堆报错，cv到csdn查了一下，c++引号内容是const char*型的所以转一下类型就好

 习题2 栈的应用 -- 表达式求值

1全部代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack {
	int top;
	int data[STACK_MAX_SIZE];
} *CharStackPtr, CharStack;


void outputStack(CharStackPtr paraStack) {
	for (int i = 0; i <= paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}
	printf("n");
}

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;
	return resultPtr;
}

void push(CharStackPtr paraStackPtr, int paraValue) {
	//1检查栈内是否还有空间
	if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
		printf("栈满，无法继续添加元素n");
		return;
	}
	//2移动栈顶
	paraStackPtr->top++;
	//3添加元素进栈
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

char pop(CharStackPtr paraStackPtr) {
	//1检查栈内是否有元素
	if (paraStackPtr->top < 0) {
		printf("栈空，无法取出元素n");
		return '';
	}
	//2移动栈顶
	paraStackPtr->top--;
	//3添加元素
	return paraStackPtr->data[paraStackPtr->top + 1];
}

int isEmpty(CharStackPtr paraStackptr) {
	if (paraStackptr->top != -1) {
		return 1;
	}
	return 0;
}

char GetTop(CharStackPtr s) { //取栈顶元素，先判空
	char x;
	if (!isEmpty(s)) {
		return 0;
	} else
		x = s->data[s->top];
	return x;
}


int Judge(char top) { //用于判断字符ch是否是优先运算符
	int x;
	switch (top) {
		case '(':
			x = 0;
			break;
		case '+':
		case '-':
			x = 1;
			break;
		case '*':
		case '/':
			x = 2;
			break;
		case ')':
			x = 3;
			break;
	}
	return x;
}

double eval(double b, double a, char top) { //用于计算当前的值，并将该值返回
	double c = 0;
	switch (top) {
		case '+':
			c = b + a;
			break;
		case '-':
			c = b - a;
			break;
		case '*':
			c = b * a;
			break;
		case '/':
			if (a == 0) {
				printf("分母为零!n");
				return 0;
			} else
				c = b / a;
			break;
		default:
			printf("输入的字符非法!n");
			break;
	}
	return c;
}


void expressionEvaluationTest() {
	char str[1000];
	printf("请输入算术表达式(功能：+，-，*，/)n");
	scanf("%s", str);
	CharStackPtr op = charStackInit();     //初始化操作符栈
	CharStackPtr num = charStackInit();     //初始化操作数栈
	int i, j;                               //i,j为循环变量，a,b接收从操作数栈中出栈的元素
	double f;                               //接收将字符数转换为浮点数的值
	double a = 0;
	double b = 0;
	double c = 0;
	char d[1000];                           //储存字符串中连续的‘数’
	char top = 0;                          //接收从操作符栈中出栈的元素
	for (i = 0; str[i]; i++) {             //将字符串中的元素按顺序入到栈中
		switch (str[i]) {
			case '(':
			case '+':
			case '-':
				
				if ((!isEmpty(op)) || (Judge(str[i]) > Judge(GetTop(op)))||(str[i]=='(')) { 
					push(op, str[i]);
				} else {
					a = pop(num); //接收从 操作数栈 中出栈的元素
					b = pop(num); //接收从 操作数栈 中出栈的元素
					top = pop(op);//接收从 操作符栈 中出栈的元素
					c = eval(b, a, top);
					push(num, c);
					//将计算后的值压入 操作数栈 中
					push(op, str[i]);
				}
				break;
			case '*':
			case '/':
				if ((!isEmpty(op)) || (Judge(str[i]) > Judge(GetTop(op)))||(str[i]=='(')) {
					//当操作符栈为空或者该操作符的优先级大于栈顶元素的优先级时入栈保存
					push(op, str[i]);
				} else {
					a = pop(num);//接收从 操作数栈 中出栈的元素
					b = pop(num);//接收从 操作数栈 中出栈的元素
					top = pop(op);//接收从 操作符栈 中出栈的元素
					c = eval(b, a, top);
					push(num,c);
					//将计算后的值压入 操作数栈 中
					push(op,str[i]);
				}
				break;
			case ')':
				while (isEmpty(op)&&GetTop(op)!='(') { //当操作符栈不为空的时候执行
					a = pop(num);//接收从操作数栈中出栈的元素
					b = pop(num);//接收从操作数栈中出栈的元素
					top = pop(op);//接收从操作符栈中出栈的元素
					c = eval(b, a, top);
					push(num, c);
					//将计算后的值压入操作数栈中
					break;
				}
			case '':
				break;
			default:
				j = 0;
				do {
					d[j++] = str[i++];
				}while (str[i] >= '0' && str[i] <= '9');  //可存入一个或多个数字字符
				d[j] = NULL;                  //将输入的连续多个数字字符拼成了字符串
				i--;
				f = atof(d); 	//转为浮点数
				push(num,f);    //将转换后的数压入操作数栈中
				break;
		}
	}
	while (isEmpty(op)) { //当操作符栈不为空的时候执行
		a = pop(num);//接收从操作数栈中出栈的元素
		b = pop(num);//接收从操作数栈中出栈的元素
		top = pop(op);//接收从操作符栈中出栈的元素
		c = eval(b, a, top);
		push(num, c);
		//将计算后的值压入操作数栈中
	}
	printf("该表达式的计算结果为：") ;
	int sum=pop(num);
	printf("%dn",sum);

}


int main(){
		expressionEvaluationTest();
		return 0;
	}

 测试结果（括号不可用，128以上数字计算出问题，已摆烂）

请输入算术表达式(功能：+，-，*，/)
3*6+2*4-8+12-3*6
该表达式的计算结果为：12

--------------------------------
Process exited after 20.11 seconds with return value 0

Press ANY key to continue...