数据结构第五天——栈及部分应用

包含栈的一些基本功能，还有部分应用，括号匹配和表达式求值

一、栈的基本功能

1.建立

typedef struct CharStack{
	int top;
	
	char data[10];
} *CharStackPtr;

2.初始化

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

3.压栈

void push(CharStackPtr paraStackPtr, int paraValue) {
	if (paraStackPtr->top >= 9) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->top ++;
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

4.出栈

char pop(CharStackPtr paraStackPtr) {
	if (paraStackPtr->top < 0) {
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	
	paraStackPtr->top --;
	return paraStackPtr->data[paraStackPtr->top + 1];
}

5.总代码

#include
#include

typedef struct CharStack{
	int top;
	
	char data[10];
} *CharStackPtr;


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


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


 
void push(CharStackPtr paraStackPtr, int paraValue) {
	if (paraStackPtr->top >= 9) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->top ++;
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}


 
char pop(CharStackPtr paraStackPtr) {
	if (paraStackPtr->top < 0) {
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	
	paraStackPtr->top --;
	return paraStackPtr->data[paraStackPtr->top + 1];
}

void pushPopTest() {
	char ch;
	int i;
	
	printf("---- pushPopTest begins. ----n");
	
	CharStackPtr tempStack = charStackInit();
	printf("After initialization, the stack is: ");
	outputStack(tempStack);
	
	for (ch = 'a'; ch < 'm'; ch ++) {
		printf("Pushing %c.n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
	
	for (i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("Pop %c.n", ch);
		outputStack(tempStack);
	}
	
	printf("---- pushPopTest ends. ----n");
}


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

运行结果

二、 括号匹配

前面其实和第一部分相差不大，就只把核心代码列出来

int bracketMatching(char *paraString, int paraLength) {
	int i;
	
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
	
	for (i = 0; i < paraLength; i ++) {
		tempChar = paraString[i];
		
		switch(tempChar) {
			case '(':
			case '[':
			case '{':
				push(tempStack, tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '(') {
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '[') {
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '{') {
					return 0;
				}
				break;
			default:
				break;
		}
	}
	
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return 0;
	}
	
	return 1;
}

一开始加入了‘#’号到栈里，方便后续的判断

原理就是当读入左括号，如‘（’、‘[’、‘{’时，将它们压入栈，当读到右括号时‘)’、']'、'}'，判断栈顶的符号是否符合，符合则返回1，否则返回0

最后加入一个判断，当式子里左右括号数量不对等时，返回0

总代码

#include
#include

typedef struct CharStack{
	int top;
	
	char data[10];
} *CharStackPtr;


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


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


 
void push(CharStackPtr paraStackPtr, int paraValue) {
	if (paraStackPtr->top >= 9) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->top ++;
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}


 
char pop(CharStackPtr paraStackPtr) {
	if (paraStackPtr->top < 0) {
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	
	paraStackPtr->top --;
	return paraStackPtr->data[paraStackPtr->top + 1];
}

int bracketMatching(char *paraString, int paraLength) {
	int i;
	
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
	
	for (i = 0; i < paraLength; i ++) {
		tempChar = paraString[i];
		
		switch(tempChar) {
			case '(':
			case '[':
			case '{':
				push(tempStack, tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '(') {
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '[') {
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '{') {
					return 0;
				}
				break;
			default:
				break;
		}
	}
	
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return 0;
	}
	
	return 1;
}

void bracketMatchingTest() {
	char *tempExpression = "[2 + (1 - 3)] * 4";
	int tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %dn", tempExpression, tempMatch);
	
	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %dn", tempExpression, tempMatch);
	
	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %dn", tempExpression, tempMatch);
	
	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %dn", tempExpression, tempMatch);
	
	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %dn", tempExpression, tempMatch);
}

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

运行结果

三、表达式求值

思路还是借鉴的学长的思路，只能说确实很厉害

1、创建

typedef struct CharAndIntStack{
	int topInt;
	int topChar;
	
	int dataInt[100];
	char dataChar[100];
} *CharAndIntStackPtr;

 这个其实里面包含了两个栈，一个专门用来存放数字，一个用来存放符号，等下计算的时候方便使用

2、压栈

void pushInt(CharAndIntStackPtr paraStackPtr, int paraValue) {
	if (paraStackPtr->topInt >= 99) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->topInt ++;
	
	paraStackPtr->dataInt[paraStackPtr->topInt] = paraValue;
}

void pushChar(CharAndIntStackPtr paraStackPtr, char paraValue) {
	if (paraStackPtr->topChar >= 99) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->topChar ++;
	
	paraStackPtr->dataChar[paraStackPtr->topChar] = paraValue; 
}

同理，有两种栈，就有两种压栈方式，但是原理相差不大

3、出栈

int popInt(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topInt < 0) {
		printf("Cannot pop element: stack empty.n");
		return 0;
	}
	
	paraStackPtr->topInt --;
	
	return paraStackPtr->dataInt[paraStackPtr->topInt + 1];
}

char popChar(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topChar < 0) {
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	
	paraStackPtr->topChar --;
	
	return paraStackPtr->dataChar[paraStackPtr->topChar + 1];
}

4、判断优先级

int Priority(char temp) {
	if (temp == '+' || temp == '-') {
		return 1;
	} else if (temp == '*' || temp == '/') {
		return 2;
	} else {
		return 0;
	}
} 

判断+、-、*、/的优先级

5、判断数字

int judgenumber(char temp) {
	if (temp >= '0' && temp <= '9') {
		return 1;
	} else {
		return 0;
	}
}

6、计算

void compute(CharAndIntStackPtr tempStack) {
	int b = popInt(tempStack);
	int a = popInt(tempStack);
	char c = popChar(tempStack);
	int x;
	if (c == '+') {
		x = a + b;
	} else if (c == '-') {
		x = a - b;
	} else if (c == '*') {
		x = a * b;
	} else {
		x = a / b;
	}
	pushInt(tempStack, x);
}

7、判断符号栈里是否还有剩余

int judgeSize(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topChar == -1) {
		return 0;
	}
	
	if (paraStackPtr->dataChar[paraStackPtr->topChar] != '') {
		return 1;
	} else {
		return 0;
	}
}

8.总代码

#include
#include

typedef struct CharAndIntStack{
	int topInt;
	int topChar;
	
	int dataInt[100];
	char dataChar[100];
} *CharAndIntStackPtr;


  
CharAndIntStackPtr charandintStackInit() {
	CharAndIntStackPtr resultPtr = (CharAndIntStackPtr)malloc(sizeof(struct CharAndIntStack));
	
	resultPtr->topChar = -1;
	resultPtr->topInt = -1;
	
	return resultPtr;
}


 
void pushInt(CharAndIntStackPtr paraStackPtr, int paraValue) {
	if (paraStackPtr->topInt >= 99) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->topInt ++;
	
	paraStackPtr->dataInt[paraStackPtr->topInt] = paraValue;
}

void pushChar(CharAndIntStackPtr paraStackPtr, char paraValue) {
	if (paraStackPtr->topChar >= 99) {
		printf("Cannot push element: stack full.n");
		return;
	}
	
	paraStackPtr->topChar ++;
	
	paraStackPtr->dataChar[paraStackPtr->topChar] = paraValue; 
}


 
int popInt(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topInt < 0) {
		printf("Cannot pop element: stack empty.n");
		return 0;
	}
	
	paraStackPtr->topInt --;
	
	return paraStackPtr->dataInt[paraStackPtr->topInt + 1];
}

char popChar(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topChar < 0) {
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	
	paraStackPtr->topChar --;
	
	return paraStackPtr->dataChar[paraStackPtr->topChar + 1];
}


 
int Priority(char temp) {
	if (temp == '+' || temp == '-') {
		return 1;
	} else if (temp == '*' || temp == '/') {
		return 2;
	} else {
		return 0;
	}
} 


  
int judgenumber(char temp) {
	if (temp >= '0' && temp <= '9') {
		return 1;
	} else {
		return 0;
	}
}


 
void compute(CharAndIntStackPtr tempStack) {
	int b = popInt(tempStack);
	int a = popInt(tempStack);
	char c = popChar(tempStack);
	int x;
	if (c == '+') {
		x = a + b;
	} else if (c == '-') {
		x = a - b;
	} else if (c == '*') {
		x = a * b;
	} else {
		x = a / b;
	}
	pushInt(tempStack, x);
}


  
int judgeSize(CharAndIntStackPtr paraStackPtr) {
	if (paraStackPtr->topChar == -1) {
		return 0;
	}
	
	if (paraStackPtr->dataChar[paraStackPtr->topChar] != '') {
		return 1;
	} else {
		return 0;
	}
}

int main() {
	CharAndIntStackPtr tempStack = charandintStackInit();
	char test[100];
	gets(test);
	
	int testLength = 0, i;
	for (i = 0; test[i] != ''; i ++) {
		testLength ++;
	}
	
	for (i = 0; i < testLength; i ++) {
		char c = test[i];
		
		if (judgenumber(c) == 1) {
			int x = 0, j = i;
			while (j < testLength && judgenumber(test[j])) {
				x = x * 10 + test[j ++] - '0';
			}
			i = j - 1;
			pushInt(tempStack, x);
		} else if (c == '(') {
			pushChar(tempStack, c);
		} else if (c == ')') {
			while (tempStack->dataChar[tempStack->topChar] != '(') {
				compute(tempStack);
			}
			popChar(tempStack);
		} else {
			while (judgeSize(tempStack) == 1 && tempStack->dataChar[tempStack->topChar] != '(' && Priority(tempStack->dataChar[tempStack->topChar]) >= Priority(c)) {
				compute(tempStack);
			}
			pushChar(tempStack, c);
		}
	}
	
	while (judgeSize(tempStack) == 1) {
		compute(tempStack);
	}
	
	printf("%d", tempStack->dataInt[tempStack->topInt]);
	
	return 0;
}

9、测试结果

测试用例1：12*（2*（1+2））

测试用例2：81/(3*3)-10

总结

1、注意的点有运算的数不知一位数，而是两位数，三位数，当读取的第一个值是数字的话，得往后再判断判断，是否为多位数

2、运行完之后应检查符号栈里是否有剩余

3、存在的缺陷，我没有做除以0的判断（等以后有空在做），同时输入负数时不能直接输入，可以用（0-x）的形式输入

4、在写括号匹配时，swtich函数，括号里输入一个判断式子时，会直接进入第一个case（大概），导致一致判断错误，所以写的时候还得注意规范