2021-10-26

学习了数据结构里的栈，偶然看到课后题里面有一个中缀表达式转后缀表达式的（逆波兰表达式），感觉挺有趣的，就写了一个练练手，有些地方的逻辑我弄的挺别扭的，哈哈，C语言确实有点不方便

//#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define MAXSIZE 50
#define TRUE 1
#define FAlSE 0
typedef char ElementType;
//定义符号栈
typedef struct Sstack {
	int length;
	ElementType stack[MAXSIZE];
} signStack;
//定义表达式结构
typedef struct exp {
	int length;
	ElementType exp[MAXSIZE];
} expression;
//判断符号优先级
int sortNumber(char e) {
	int order = 0;
	switch (e)
	{
	case ']':order = 0; break;
	case ')':order = 1; break;
	case '+':
	case '-':order = 2; break;
	case '*':
	case '/':order = 3; break;
	case '(':order = 4; break;
	case '[':order = 5; break;
	}
	return order;
}
//转换函数，一段挺有趣的代码
int priorityCheck(char current, char preview)
{
	int cur = sortNumber(current);
	int pre = sortNumber(preview);
	switch (cur)
	{
	case 0: {
		if (pre == 5)
			return TRUE;
		else
			return FAlSE;
		break;
	}
	case 1: {
		if (pre == 4)
			return TRUE;
		else
			return FAlSE;
		break;
	}
	case 2: {
		if (pre == 2 || pre == 3)
			return FAlSE;
		else if (pre >= 4)
			return TRUE;
		else
			return TRUE;
		break;
	}
	case 3: {
		if (pre == 3)
			return FAlSE;
		else
			return TRUE;
		break;
	}
	case 4:
	case 5:return TRUE; break;
	}

}
//压栈函数
int push(signStack* target, ElementType e) {
	if (target->length == MAXSIZE) {
		return FAlSE;
	}
	else {
		target->stack[target->length++] = e;
		return TRUE;
	}
}
//出栈函数
int pop(signStack* target, ElementType* e) {
	if (target->length == 0) {
		return FAlSE;
	}
	else {
		*e = target->stack[--target->length];
		return TRUE;
	}
}
//中缀表达式转后缀表达式函数
int conversion(const expression* source, expression* target) {
	signStack sig;
	sig.length = 0;
	int position = 0;
	int sigposition;
	char element;
	int start = 0;//数字开始标志
	int end = 0;//数字结束标志
	while (position < source->length) {
		element = source->exp[position];
		if (element >= 'a' && element <= 'z' || element >= 'A' && element <= 'Z') {
			target->exp[target->length++] = element;
			start = 0;
			end = 0;
		}
		else if (element >= '0' && element <= '9') {
			target->exp[target->length++] = element;
			start = 1;
		}
		else if (sig.length == 0) {
			if (!push(&sig, element)) {
				printf("符号栈溢出，程序终止");
				return FAlSE;
			}
			else {
				end = 1;
				if (start == 1 && end == 1)
					target->exp[target->length++] = ' ';
				start = 0;
				end = 0;
			}
		}
		else {
			end = 1;
			if (start == 1 && end == 1)
				target->exp[target->length++] = ' ';
			start = 0;
			end = 0;
			sigposition = sig.length - 1;
			while (sigposition >= 0 && !priorityCheck(element, sig.stack[sigposition--])) {
				pop(&sig, &target->exp[target->length++]);
			}
			if (element != ')' && element != ']')
				push(&sig, element);
			else {
				pop(&sig, &target->exp[target->length++]);
				target->length--;
			}
		}
		position++;
	}
	while (sig.length > 0) {
		pop(&sig, &target->exp[target->length++]);
	}
	return TRUE;
}
int length(char* str) {
	int len = 0;
	while (str[len] != '')
		len++;
	return len;
}
int main() {
	int i = 0;
	expression s1, s2;
	s1.length = 0;
	s2.length = 0;
	scanf("%s", s1.exp);
	s1.length = length(s1.exp);
	conversion(&s1, &s2);
	for (i = 0; i < s2.length; i++)
		printf("%c", s2.exp[i]);
	return 0;
}

有啥问题欢迎留言