[C++知识库]四则运算c语言实现

直接上代码, 解析在后面

#include <stdio.h>
#define LEN 100

void mul(int* pre, int* oper, int* next) {
	*next *= *pre;
	*pre = 0;
	*oper = '+';
}

void div(int* pre, int* oper, int* next) {
	*next = *pre / *next;
	*pre = 0;
	*oper = '+';
}

void add(int* pre, int* next) {
	*pre += *next;
	*next = 0;
}

void sub(int* pre, int* next) {
	*pre -= *next;
	*next = 0;
}

void clear(int formula[]) {
	for (int i = 0; i < LEN; i++) formula[i] = 0;
}

void input(int formula[]) {
	int i = 0;
	int x = 0;
	for (;;) {
		scanf("%c", &x);
		if (x == '\n') {
			formula[++i] = '\n';
			break;
		}
		else if (x <= '9' && x >= '0') {
			formula[i] = formula[i] * 10 + (x - '0');
		}
		else if(x == '+' || x=='-' || x=='*' || x== '/') {
			formula[++i] = x;
			i++;
		}
		else if (x == '(') {
			formula[i++] = x;
		}
		else if (x == ')') {
			formula[++i] = x;
		}
	}
}

void move(int start, int len, int formula[]) {
	int index = start + len;
	if (start != 0) {
		while (formula[++index] != '\n') {
			formula[index - len - 1] = formula[index];
			formula[index] = 0;
		}
	}
}

void operation(int start, int formula[]) {
	int i = start;
	int value = 0;
	int len = 0;
	for (;;) {
		value = formula[i];
		if (value == '\n' || value == ')') {
			len = i - start;
			break;
		}
		else if(value == '(') operation(i + 1, formula);
		else if (formula[i + 1] == '(') operation(i + 2, formula);
		if (value == '*') {
			mul(&formula[i - 1], &formula[i], &formula[i + 1]);
			i++;
		}
		else if (value == '/') {
			div(&formula[i - 1], &formula[i], &formula[i + 1]);
			i++;
		}
		else if (value == '+' || value == '-') i++;
		i++;
	}
	for (;;) {
		i -= 2;
		if (i < start) break;
		else value = formula[i];
		if (value == '+') add(&formula[i - 1], &formula[i + 1]);
		else if (value == '-') sub(&formula[i - 1], &formula[i + 1]);
	}
	if (i >= 0) {
		formula[i] = formula[i + 1];    //处理括号
	}
	move(start, len, formula);
}

int main() {
	int formula[LEN];
	clear(formula);
	input(formula);
	operation(0, formula);
	printf("%d", formula[0]);
	return 0;
}

先说总体思路:

1. 首先读取输入内容, 将输入的字符串按数字与符号处理好, 装入一个数组中, 以换行符\n为结束标志, 当然你也可以不事先装入, 便读取边运算, 但那样写出来会更加复杂
2. 运算方法. 这里读取事先拿到的数组, 一共需要扫描两遍, 第一遍处理乘除法, 扫描完成后, i计数到末尾, 再从末尾扫回头, 此时处理加减法
3. 对于括号内容, 采用递归处理, 重复2的运算方法

具体实现以及技术细节:

1. 对于第一遍扫描处理乘除法, 把得到的结果置入后一个数(其实放前面也可以), 再把前一个数置0, 运算符号置为+, 例如2*3=0+6. 对于第二遍扫描处理加减法, 把后一个数置0, 运算结果放到前一个数, 这样, 当第二遍扫回头的时候, 整个式子的运算结果便推到了array[0]. 运算完毕.
2. 对于括号的处理, 有两种情况, 一种情况是在第一遍扫描时(必须在第一遍扫描处理), 如果乘除法后接的不是数字, 那么不要马上直接进行运算, 此时应该对array[i+1]做检查, 进行递归运算. 另一种情况是括号在字符串开头, 或者嵌套括号在头部堆积, 如(((((, 此时array[i+1]不可捕捉. 应该设置array[i]. 还有一个配合处理的方法是移动函数, 在括号运算结束之时, 括号内的运算遗留以及括号应该全部清除, 此时将后方括号外的算式移动到前方拼接
3. 结果取出, 主式运算结果是放在数组头部的, 对于括号的式子, 得到的结果并不是式子的头部, 而是取带了左括号(的位置.

可能存在的疑问:

? ? ?1. 为什么要采取扫描两遍的方法, 与传统的栈处理相比如何?

? ? ? ? 答: 其实时间复杂度两者应该是一样的, 因为无论使用哪种方法, 都无法预知后方连续的优先级顺序, 如果使用栈, 那么加减法同样不会马上得到处理, 而是先探查后方运算存在更高的优先级, 再做处理后弹栈, 那么反复的出栈与入栈操作步数应该也是O(2n). 我认为这种写法会更加清晰, 且不需要复杂的数据结构.

? ? ?2. move有无必要?

? ? ? ? 答: 这里存在另一种思路, 就是在第二遍扫描时, 顺带将处理后的数据全部用0填平, 那么可以省略对数组的移动, 但另一个与之带来的问题是, 此时退出括号后, i的指向是左括号(, 那么意味着对于后面填0的数组段同样要走一遍, 加上第二遍扫描, 这个步数是括号数据的两倍, 那么move的步数呢? move的步数是数组剩余元素的个数, 如果数组剩余元素很大, 即式子很长, 括号的内容又很少, 那么相交于填0的方法, 步数会更多. 对于填0的办法, 可以通过捕获这个括号的长度, 让两次扫描跳过这个括号即可.

? ? ?3. clear函数有什么用?

? ? ? ? 答: 如果你只想进行一遍运算. 确实无用. 你甚至可以用calloc代替, 如果你想反复运算, 并复用数组, 那你最好使用clear方法.

优化与改进:

1. 可以考虑使用链表的方式存储处理, 那么对于多余代码清除, 如括号, 会更方便, 但链表的代码书写量会更大
2. 在输入时应该做安全检查, 这里没有考虑
3. 没考虑浮点数, 除法的结果会丢失精度,如果有要求, 请改为double数组.
4. 不支持直接写负号表示负数, 你可以写(0-1)*num. 这里提供一种思路: 在input时设置一个tab表示当前数字的正负数标志, 再添加一条语句?if (x == '-' && formula[i] == 0) tab = -1; 因为根据设计, 如果当前数组元素为空, 它便意味着待接受一个数字, 再在else if (x <= '9' && x >= '0')内对tab做出相应判断做出相应处理即可, 记得切换tab状态. 我更倾向于使用第一种办法处理, 因为直接在数字前与符号后添加一个负号显得很不优雅, 那看上去更像是一种非法书写.
5. 如果你想要更精简, 你可以把mul, div, add, sub都写到operation中去.
6. 你自己看着办吧

测试用例:

input:

(2+996*(6/3-9*(((4+2)*100-66)*4)))+3

output

-19145107