C语言堆栈实现计算器（求后缀表达式）

#include
#include 
#include
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef double status;
typedef char ElemType;
typedef struct SqStack {
	ElemType data[MAXSIZE];
	int top;
}SQTA;
typedef struct SqStack* StackChar;
typedef int ElemTypes;
typedef struct SqStacks {
	ElemTypes data[MAXSIZE];
	int top;
}SQTAs;

typedef struct SqStacks* StackInt;
int begin();
int transform(char expression[]);
int count(char expressionChar[], int expressionInt[]);


int transform(char expression[]) {

	char expressionChar[100] = {};
	int expressionInt[100] = {};
	char* p = expression;
	int a = 0;
	int index = 0;
	int flag = 1;
	StackChar zc = (StackChar)malloc(sizeof(SQTA));
	zc->top = -1;

	do {

		if (*p >= 48 && *p <= 57) {
			a *= 10;
			a += *p - 48;
			flag = 1;
		}
		else {
			if (flag == 1) {
				expressionInt[index] = a;
				expressionChar[index] = '!';
				index++;
				a = 0;
			}
			if (*p == NULL) {
				while (zc->top != -1) {
					expressionChar[index] = zc->data[zc->top];
					index++;
					zc->top--;
				}

				break;
			}
			else if (zc->top == -1 || *p == '(') {
				zc->top++;
				zc->data[zc->top] = *p;
			}
			else if (*p == ')') {
				do {
					if (zc->data[zc->top] == '(') {
						zc->top--;
						break;
					}
					else {

						expressionChar[index] = zc->data[zc->top];
						index++;
						zc->top--;
					}
				} while (1);

			}
			else if (*p == '*' || *p == '/') {
				while (zc->top >= 0 && zc->data[zc->top] == '*' || zc->data[zc->top] == '/') {
					expressionChar[index] = zc->data[zc->top];
					index++;
					zc->top--;
				}
				zc->top++;
				zc->data[zc->top] = *p;

			}
			else if (*p == '+' || *p == '-') {
				while (zc->top >= 0 && zc->data[zc->top] != '(') {
					expressionChar[index] = zc->data[zc->top];
					index++;
					zc->top--;
				}

				zc->top++;
				zc->data[zc->top] = *p;

			}

			flag = 0;


		}
		p++;
	} while (1);
	int i = 0;
	printf("n");
	while (expressionInt[i] != NULL || expressionChar[i] != NULL) {
		if (expressionInt[i] != NULL) {
			printf("%d", expressionInt[i]);

		}
		else if (expressionChar[i] != '!') {
			printf("%c", expressionChar[i]);
		}
		i++;
	}
	printf("n");

	int counts = 0;
	counts = count(expressionChar, expressionInt);
	return counts;
}
int count(char expressionChar[], int expressionInt[]) {
	int i = 0;
	StackInt zi = (StackInt)malloc(sizeof(SQTAs));
	zi->top = -1;
	int count = 0;
	int count1 = 0, count2 = 0;
	while (expressionInt[i] != NULL || expressionChar[i] != NULL) {
		if (expressionInt[i] != NULL) {
			zi->top++;
			zi->data[zi->top] = expressionInt[i];

		}
		else if (expressionChar[i] != '!') {
			count2 = zi->data[zi->top];
			zi->top--;
			count1 = zi->data[zi->top];
			if (expressionChar[i] == '+') {
				count = count1 + count2;
			}
			else if (expressionChar[i] == '-') {
				count = count1 - count2;
			}
			else if (expressionChar[i] == '*') {
				count = count1 * count2;
			}
			else if (expressionChar[i] == '/') {
				count = count1 / count2;
			}
			zi->data[zi->top] = count;
		}

		i++;
	}
	count = zi->data[zi->top];
	zi->top--;

	return count;
}
int begin() {
	char expression[100] = "";
	printf("请输入您要计算的表达式：n");
	scanf("%99s", &expression);
	printf("n后缀表达式：n");
	printf("n计算结果是：%dnn", transform(expression));
}
int main() {
	while (1) {
		begin();
	}
	return 1;
}

程序中一个操作符栈以及一个操作数栈，分别用来存储运算符和数字。定义一个大小为N=100的堆栈，如果运算符栈顶等于N-1，则堆栈为满，输入表达式，转化为后缀表达式，把扫描到的字符，依次放入字符栈。对运算数进行同样的压栈和判断字符的优先级，然后对压入堆栈的运算数和运算符进行出栈操作，取出栈顶的运算符和运算数，然后进行计算，最后输出结果；时间复杂度和空间复杂度都为O(n)。