中序计算式的计算器模型C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <stdbool.h>

#define INIT_SIZE 100
#define INCRE_SIZE 10
#define OPERAND 1
#define OPERATOR 2

char _BUFFER[1000];
int _POS;

char myGetchar();
void myUnGetchar(char c);

typedef enum operator_et
{
	LBR,  // 左括号
	RBR,  // 右括号
	ADD,  // 加
	SUB,  // 减
	MUL,  // 乘
	DIV,  // 除
	INV,  // 乘方
	SIN,  // sin
	COS,  // cos
	END   // 结束标志
}operator_et;

typedef double data_t;
typedef struct cal_t
{
	data_t *operand;
	int *operator;
	int operand_size;
	int operator_size;
	int operand_top;
	int operator_top;
}cal_t;
typedef cal_t* cal_pt;

// 初始化栈
cal_pt calInit();
// 销毁栈
void calFree(cal_pt cal);
// 压进操作符
void calOperatorPush(operator_et operator, cal_pt cal);
// 弹出操作符
operator_et calOperatorPop(cal_pt cal);
// 压进操作数
void calOperandPush(data_t operand, cal_pt cal);
// 弹出操作数
data_t calOperandPop(cal_pt cal);
// 操作符优先级比较，优先级大于栈顶返回1，相等返回0，小于返回-1
int operatorCmp(operator_et top, operator_et op);
// 给操作数，进行计算
void work(operator_et op, cal_pt cal);
// 获取操作符或者操作数，返回类型
int getop(char *op);
// 主逻辑函数，进行运算
void calculator(cal_pt cal);
void __calculator(operator_et op, cal_pt cal);

int main()
{
	cal_pt cal = calInit();
	scanf("%s", _BUFFER);
	_POS = 0;
	calculator(cal);
	// 计算完成。数据栈里唯一的数字就是所需要的数据
	printf("%.3lf\n", calOperandPop(cal));
	calFree(cal);
	return 0;
}

void __calculator(operator_et op, cal_pt cal)
{
	switch(operatorCmp(cal->operator[cal->operator_top], op))
	 {
	 	case 1:  // 新运算符优先级更大，压入
	 	{
	 		calOperatorPush(op, cal);
	 		break;
	 	}
	 	case -1:  // 新运算符优先级更小，弹出计算直至没有比它更大的运算符
	 	{
	 		do
	 		{
	 			work(calOperatorPop(cal), cal);
	 		}while(operatorCmp(cal->operator[cal->operator_top], op) == -1);
	 		__calculator(op, cal);
	 		break;
	 	}
	 	case 0:  // 只有当运算符为括号或结束符时才会出现。弹出运算符，不做操作
	 	{
	 		calOperatorPop(cal);
	 		break;
	 	}
	 }
}

char myGetchar()
{
	return _BUFFER[_POS ++];
}

void myUnGetchar(char c)
{
	_POS -= 1;
}

void calculator(cal_pt cal)
{
	bool isOver = false;
	char opString[20];
	int type;
	while (!isOver)
	{
		type = getop(opString);
		if (type == OPERAND)
		{
			calOperandPush(atoi(opString), cal);
		}
		else
		{
			switch(opString[0])
			{
				case '+':
				{
					__calculator(ADD, cal);
					break;
				}
				case '-':
				{
					__calculator(SUB, cal);
					break;
				}
				case '*':
				{
					__calculator(MUL, cal);
					break;
				}
				case '/':
				{
					__calculator(DIV, cal);
					break;
				}
				case '^':
				{
					__calculator(INV, cal);
					break;
				}
				case 'c':
				{
					__calculator(COS, cal);
					break;
				}
				case 's':
				{
					__calculator(SIN, cal);
					break;
				}
				case '(':
				{
					__calculator(LBR, cal);
					break;
				}
				case ')':
				{
					__calculator(RBR, cal);
					break;
				}
				case '#':
				{
					isOver = true;
					__calculator(END, cal);
					break;
				}
			}
		}
	}
}

int getop(char *op)
{
	int pos = 0;
	char c = myGetchar();
	// 去除空白字符串
	while (isblank(c))
	{
		c = myGetchar();
	}
	// 判断是字符还是数字
	if (isdigit(c))
	{
		while (isdigit(c))
		{
			op[pos ++] = c;
			c = myGetchar();
		}
		myUnGetchar(c);
		op[pos] = '\0';
		return OPERAND;
	}
	op[pos ++] = c;
	op[pos] = '\0';
	if (op[0] == 'c' || op[0] == 's')  // cos或sin吸收后面的两个符号
	{
		myGetchar();
		myGetchar();
	}
	return OPERATOR;
}

void work(operator_et op, cal_pt cal)
{
	switch(op)
	{
		case ADD:  // 加法运算，弹出两个操作数，运算后压回去
		{
			calOperandPush(calOperandPop(cal) + calOperandPop(cal), cal);
			break;
		}
		case SUB: // 减法运算
		{
			data_t tmp = calOperandPop(cal);
			calOperandPush(calOperandPop(cal) - tmp, cal);
			break;
		}
		case MUL: // 乘法运算
		{
			calOperandPush(calOperandPop(cal) * calOperandPop(cal), cal);
			break;
		}
		case DIV: // 除法运算
		{
			data_t tmp = calOperandPop(cal);
			calOperandPush(calOperandPop(cal) / tmp, cal);
			break;
		}
		case INV: // 乘方运算
		{
			data_t tmp = calOperandPop(cal);
			calOperandPush(pow(calOperandPop(cal), tmp), cal);
			break;
		}
		case SIN: // 正弦运算
		{
			calOperandPush(sin(calOperandPop(cal)), cal);
			break;
		}
		case COS: // 余弦运算
		{
			calOperandPush(cos(calOperandPop(cal)), cal);
		}
	}
}

int operatorCmp(operator_et top, operator_et op)
{
	// 规则：
	// 1. 栈顶元素是左括号时，除右括号外任何操作符优先级大于栈顶元素。碰到结束符则说明输入错误
	// 2. 新操作符是左括号时，左括号优先级大于任何栈顶元素
	// 3. 新操作符是右括号时，除左括号外右括号小于任何栈顶元素
	// 4. 同级别操作符，除了括号与结束符相等外，新操作符优先级均小于栈顶元素
	// 5. 结束符的优先级小于所有的运算符
	// 6. 优先级排序（不包括括号）：结束符，加减法，乘除，乘方、三角函数
	int res;
	switch(op)
	{
		case LBR:  // 新操作符是左括号时，左括号优先级大于任何栈顶元素
		{
			res = 1;
			break;
		}
		case RBR:  // 新操作符是右括号时，除左括号外右括号小于任何栈顶元素
		{
			res = (top == LBR) ? 0 : -1;
			break;
		}
		case END:  // 最低级的运算符，将所有栈内元素取出
		{
			if (top == LBR)
			{
				fprintf(stderr, "wrong Input!\n");
				exit(-1);
			}
			res = (top == END) ? 0 : -1;
			break;
		}
		case ADD:
		case SUB:  // 次低级的运算符，大于结束符与栈顶左括号，小于其它任何运算符
		{
			res = (top == END || top == LBR) ? 1 : -1;
			break;
		}
		case MUL:
		case DIV:  // 大于结束符、栈顶左括号、加法与减法，小于其它任何运算符。小于COS、SIN、INV、同级别运算符
		{
			return (top == END || top == LBR || top == ADD || top == SUB) ? 1 : -1;
			break;
		}
		case INV:  // 次高级运算符，仅仅小于三角函数、同级别运算符，大于任何其它级别运算符
		{
			res = (top == COS || top == SIN || top == INV) ? -1 : 1;
			break;
		}
		case COS:
		case SIN:  // 最高级别运算符，直接压入，小于同级别
		{
			res = (top == COS || top == SIN) ? -1 : 1;
			break;
		}
	}
	return res;
}

data_t calOperandPop(cal_pt cal)
{
	return *(cal->operand + cal->operand_top --);
}

void calOperandPush(data_t operand, cal_pt cal)
{
	if (++ cal->operand_top >= cal->operand_size)
	{
		cal->operand_size += INIT_SIZE;
		cal->operand = (data_t *)realloc(cal->operand, sizeof(data_t) * cal->operand_size);
	}
	*(cal->operand + cal->operand_top) = operand;
}

operator_et calOperatorPop(cal_pt cal)
{
	return *(cal->operator + cal->operator_top --);
}

void calOperatorPush(operator_et operator, cal_pt cal)
{
	if (++ cal->operator_top >= cal->operator_size)
	{
		cal->operator_size += INCRE_SIZE;
		cal->operator = (int *)realloc(cal->operator, sizeof(int) * cal->operator_size);
	}
	*(cal->operator + cal->operator_top) = operator;
}

void calFree(cal_pt cal)
{
	free(cal->operator);
	free(cal->operand);
	cal->operator = NULL;
	cal->operand = NULL;
	cal->operator_size = cal->operand_size = 0;
	cal->operator_top = cal->operand_top = -1;
}

cal_pt calInit()
{
	cal_pt cal = (cal_pt)malloc(sizeof(cal_t));
	cal->operator_size = cal->operand_size = INIT_SIZE;
	cal->operator_top = cal->operand_top = -1;
	cal->operator = (int*)malloc(sizeof(int) * INIT_SIZE);
	cal->operand = (data_t *)malloc(sizeof(data_t) * INIT_SIZE);
	calOperatorPush(END, cal);
	return cal;
}

代码解释

首先，建立一个全局字符串数组BUFFUR，以便进行字符串操作
其次，建立两个栈：操作数栈与操作符栈
总体的流程如下：

1. 取出一个操作数或操作符，
2. 如果是操作数，则直接压入操作数栈
3. 如果是操作符，与栈顶元素进行优先级比较（操作符栈在初始化时加入了一个结束符#方便计算）
4. 若新操作符的优先级更大，则压入栈
5. 若新操作符的优先级更小，则将栈顶元素弹出进行运算，然后再回到第三步
6. 若新操作符的优先级等于栈顶元素，则弹出栈顶元素（不进行运算）
7. 回到1，直至取到#，执行最后一次操作、清空操作符栈后结束

优先级比较的规则：

1. 总体优先级（从低到高）：结束符#，加减法，乘除法，乘方运算，三角函数运算
2. 当栈顶元素与新操作符优先级相同时，除非新元素为括号或#，否则默认新操作符的优先级更低
3. 当栈顶元素为左括号时，除了右括号优先级与其相同外，任何操作符优先级均高于栈顶元素。若碰到结束符#，则说明输入括号不匹配，报错退出
4. 当新元素为左括号时，默认其优先级高于任何运算符
5. 当新元素为右括号时，默认其优先级低于除了左括号外的任何运算符

举例：70+cos(3+2/2/3^2-1)*(4-3)#
操作符栈事先加入了一个#方便计算

1. 取操作数70，压入栈，操作数栈：70
2. 取操作符+，优先级高于#，压入栈，此时操作符栈：#, +
3. 取操作符cos，优先级高于+，压入栈，此时操作符栈：#, +, cos
4. 取操作符(，默认优先级高于任何操作符，压入栈，此时操作符栈：#, +, cos, (
5. 取操作数3，压入栈，操作数栈：70, 3
6. 取操作符+，默认优先级高于栈顶元素(，压入栈，此时操作符栈：#, +, cos, (, +
7. 取操作数2，压入栈，操作数栈：70, 3, 2
8. 取操作符/，优先级高于+，压入操作符栈：#, +, cos, (, +, /
9. 取操作数2，压入操作数栈：70, 3, 2, 2
10. 取操作符/，优先级等于/，默认小于栈顶元素，弹出栈顶/，弹出操作数栈中的2与2，执行计算2/2，将结果1压入栈：70, 3, 1。新操作符/优先级大于+，压入栈：#, +, cos, (, +, /
11. 取操作数3压入：70, 3, 1, 3
12. 取操作符^，优先级高于/，压入栈：#, +, cos, (, +, /, ^
13. 取操作数2压入：70, 3, 1, 3, 2
14. 取操作符-，优先级小于^，弹出^与对应操作数，执行计算3^2，将结果9压入栈：70, 3, 1, 9
15. 操作符-优先级小于/，弹出/执行计算1/9，将结果0.3333压入栈：70, 3, 0.1111
16. 操作符-与操作符+同级，依照规则默认小于栈顶，弹出+，执行计算3+0.1111，压入结果：70, 3.1111
17. 将操作符-压入栈：#, +, cos, (, -
18. 获取操作数1：70, 3.1111, 1
19. 获取操作符)，默认小于除了左括号外所有运算符，弹出-执行计算，结果：70, 2.1111
20. 弹出操作符(
21. 获取操作符*，优先级小于cos，弹出cos执行运算：70, -0.514，因为*优先级大于+，压入栈：#, +, *
22. 取括号(，依据规则压入栈
23. 取操作数4压入栈
24. 取操作符-依据规则压入栈
25. 取操作数3压入栈
26. 取操作符)，依据规则弹出-进行计算，得4-3=1，压入栈：70, -0.514, 1
27. 取得操作符#，按照顺序弹出所有操作符：-0.541 * 1 = -0.541、70 + (-0.514) 69.486
28. 计算结束

扩展：逆波兰式

链接：逆波兰式