闲来无事,写了一个比较完整的计算器

xiaoxiao2021-03-01  14

数学表达式有三种:前缀表达式,中缀表达式,后缀表达式。

中缀表达式就是我们平常见到的,如4+ 2 * 5 - 7/11 ,这个式子人算起来方便,但是计算机算起来却计算复杂。对于计算机,最好是将此式转换为前缀表达式或后缀表达式后再计算。

在写计算器之前,首先要知道一点基本知识:

1.中缀表达式转换为后缀表达式

举个例子:

4+ 2 * 5 - 7/11 这是中缀表达式,它的后缀表达式是: 4 2 5 * 7 11 / - + .(或者4 2 5 * + 7 11 / - )

其实也很简单,把中缀表达式其实就是表达式对应的二叉树的中序遍历,后缀表达式是对应二叉树的后序遍历,前缀表达式是前序遍历。

算法基本思想: 使用三个数组,一个数组保存用户输入的表达式(中缀表达式),一个数组保存后缀表达式,一个数组作为运算符的栈。 从头到尾扫描中缀表达式,对不同类型的字符按不同情况处理; 1. 如果是数字则直接放入后缀表达式数组; 2. 如果是左括号则直接入栈; 3. 如果是右括号,则把从栈顶直到对应左括号之间的运算符依次退栈[放入后缀表达式数组],并清除对应的左括号; 4. 对于运算符,如果该运算符的优先级大于栈顶优先级,则直接入栈; 若该运算符的优先级小于等于栈顶优先级,则先把栈顶运算符出栈,写入后缀表达式数组,然后再入栈;若该运算符的优先级小于等于栈顶优先级,则先把栈顶运算符出栈,写入后缀表达式数组,重复此操作,直到该运算符的优先级大于栈顶运算符的优先级,然后将该运算符入栈;(感谢 liwenhaosuper的test case,现已将错误的地方修正,并修改了相应的代码) 5. 扫描完成后,取出栈中所有运算符,写入后缀表达式数组。 注:运算符优先级: *,/ 大于 +,- 大于 (

2.计算后缀表达式 算法思想: 对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中,不需要括号,而且操作符的优先级也不再起作用了。可以通过简单的出栈如栈操作完成运算。1. 初始化一个空栈2. 从左到右读入后缀表达式3. 如果字符是一个操作数,把它压入堆栈。4. 如果字符是个操作符,弹出两个操作数,执行恰当操作,然后把结果压入堆栈。如果您不能够弹出两个操作数,后缀表达式的语法就不正确。5. 到后缀表达式末尾,从堆栈中弹出结果。若后缀表达式格式正确,那么栈应该为空。

计算器程序如下: 本程序可计算非负数学表达式,可计算非整数,假设输入合法,结果保留2位小数

#include <stdio.h> #include <stdlib.h> #define MAX_LEN 80 void convert2postfix(char *src,char *dst); float cal(char *src); int main(){ char str1[MAX_LEN],str2[MAX_LEN]; float res; gets(str1); convert2postfix(str1,str2); printf("src:%s\n",str1); printf("dst:%s\n",str2); res = cal(str2); printf("result:%.2f\n",res); return 0; } //中缀表达式转换为后缀表达式(操作符与操作数之间应有空格隔开) void convert2postfix(char *src,char *dst){ char *psrc,*pdst; char stack[MAX_LEN]; int top; top = -1; psrc = src; pdst = dst; while (*psrc != '\0') { if (*psrc >= '0' && *psrc <= '9') { *pdst = *psrc; pdst++; //加入分隔空格 if (!(*(psrc+1)>= '0' && *(psrc+1)<= '9') && *(psrc+1)!= '.') { *pdst = ' '; pdst++; } } if (*psrc == '.') { *pdst = *psrc; pdst++; } if (*psrc == '(') { stack[++top] = *psrc; } if (*psrc == ')') { while (stack[top] != '(') { *pdst = stack[top--]; pdst++; //加入分隔空格 *pdst = ' '; pdst++; } //弹出'(' top--; } if (*psrc == '*' || *psrc == '/') { if (stack[top] == '*' || stack[top] == '/') { *pdst = stack[top--]; pdst++; //加入分隔空格 *pdst = ' '; pdst++; } stack[++top] = *psrc; } if (*psrc == '+' || *psrc == '-') { while ( stack[top] == '*' || stack[top] =='/' || stack[top] == '+' || stack[top] == '-') { *pdst = stack[top--]; pdst++; //加入分隔空格 *pdst = ' '; pdst++; } stack[++top] = *psrc; } psrc++; } //扫描完成后,取出栈中所有运算符,写入后缀表达式数组。 while (top != -1 ) { *pdst = stack[top--]; *pdst++; *pdst = ' '; pdst++; } *pdst = '\0'; } //计算后缀表达式 float cal(char *src){ float stack[MAX_LEN]; float opd1,opd2; int top; char *p,*pre; top = -1; p = src; while (*p != '\0') { if (*p >= '0' && *p <= '9') { pre = p; while ((*p >= '0' && *p <= '9') || *p == '.') { p++; } *p = '\0'; stack[++top] = atof(pre); } if (*p == '+' ||*p == '-' ||*p == '*' ||*p == '/' ) { opd2 = stack[top--]; opd1 = stack[top--]; switch (*p) { case '+': stack[++top] = opd1+opd2; break; case '-': stack[++top] = opd1-opd2; break; case '*': stack[++top] = opd1*opd2; break; case '/': //更严格一点,应该处理除数为0的情况 stack[++top] = opd1/opd2; break; } } p++; } return stack[top--]; }

转载请注明原文地址: https://www.6miu.com/read-3450280.html

最新回复(0)