后缀计算器
- 格式：doc
- 大小：66.00 KB
- 文档页数：7
关于后缀计算器一程序设计的基本框架为：1 分析问题，比如对后缀表达式的字符串结构的分析，计算流程等；2 设计程序的流程，就是主函数main的流程；3 根据主函数流程确定可能使用的其它函数的名称和功能；4 程序文本的布局为各个函数块或函数单元的序列，每个函数块或函数单元的布局为本函数所使用的预定义本函数所使用的公共变量（即外部变量）的定义或声明本函数所调用的其它函数的函数原型本函数的定义（单独的一个或者紧密协作的多个函数）如果我们将上述集合称为一个function-unit的话，那么程序文本的形式就是function-unit….function-unit其中，第一个function-unit往往就是main函数。
5 有时，如果不能马上确定所要调用的函数的具体定义，那么我们可以先命名后定义。
6 本次关于后缀计算器的设计实现，包含了C语言程序设计的基本思想，请大家特别注意函数之间的3种关系，本章第2节主要说明函数之间的第1和第2种关系，即调用和被调用，传递参数和接收参数、返回结果数据这两种形式，本节则同时说明了第3种关系，并非调用和被调用而是相互协作的、通过外部变量实现信息传递的方式。
7 本次设计实现所涉及的函数尽量不使用标准函数库。
二后缀计算器的设计实现，允许使用sin函数，允许引用最近计算结果。
比如(1 – 2) * (4 + 5) 换行符等价于1空格2空格–空格4空格5空格+空格*换行符10.5 + (30 – 12.6) * 3.8 等价于10.5空格30空格12.6空格-空格3.8空格*空格+换行符sin(30 /180 * 3.1415926) 等价于30空格180空格/空格3.1415926空格*空格sin换行符在不影响正确关系的基础上，允许使用紧凑形式，因此上面表达式可以为(1 – 2) * (4 + 5) 换行符等价于1空格2–4空格5+*换行符10.5 + (30 – 12.6) * 3.8 等价于10.5空格30空格12.6-3.8*+换行符sin(30 /180 * 3.1415926) 等价于30空格180/3.1415926*sin换行符这里暂不使用带符号的数。
我们将输入的文本行字符串划分为多个子串，每个子串称为一个运算子串，这样的子串分为两类，运算数和运算符，其中换行符也称为运算符，它的作用是打印计算的结果。
这样我们设计程序的基本思想是，从输入中逐个读取运算子串，如果读入的是运算数，则将其转换为相应数值并压入栈中保存，如果是运算符，则取出栈中的运算数，计算后将结果压入栈中，其中换行运算表示取出栈中的结果数并打印而不再压入栈中。
程序（即主函数）流程：设置字符数组用于保存读入的运算子串，比如opstr[]，限制大小MAXOP = 100；设置变量用于保存运算子串的类型，比如type；当读入运算子串未结束时{ getop_若运算子串是运算数，则将其转换为数值并压入栈中；atof_ push若运算子串是四则运算符，则取出栈中数，执行相应计算并将结果压入栈中；pop push若运算子串是换行运算符，则取出栈中的结果数并打印；pop否则，输入有错误，打印错误信息；}程序结束。
上述流程中出现的操作，我们将安排函数来完成，它们的名字如上。
请注意，我们在读入运算子串时，比如12.6-，必须读入字符-才能确定12.6这个子串的完整性，这样我们就多读入了一个不属于当前子串但可能是下一个子串的一个字符，为了不影响下一个子串的读入，应该将多读入的字符退还给输入，因此，我们需要对以往惯用的函数getchar进行改进，比如#define MAXBUF 100char buffer[MAXBUF];int bufp = 0;int getch_(void){if (bufp > 0)c = buffer[--bufp];elsec = getchar();return c;}void ungetch_(int c){if (bufp < MAXBUF)buffer[bufp++] = c;elseprintf(“error: too many characters\n”);}这里，我们使用了一对相互协作的函数getch_和ungetch_来完成我们希望的读入和读入退还的功能，这两个函数的协作关系体现在它们共同使用了两个外部变量buffer[]和bufp。
请大家仔细观察，这两个外部变量也仅限于这两个函数使用，它们成为函数之间互动的第3种方式（第1种方式是调用函数向被调用函数传递参数，第2种方式是被调用函数向调用函数返回一个返回值，即return expression; 的形式）。
如果第1、2种方式反映的是函数之间的上下级关系的话，那么第3种方式将反映函数之间存在平等关系，这也是外部变量主要的使用目的。
三程序文本#include <stdio.h>此处开始main函数单元#define MAXOP 100#define NUMBER '0' 运算数子串类型#define FUNCTION '1' 函数运算符类型int getop_(char []);void push(double);double pop(void);double atof_(char []);int strcmp_(char [], char []);double sin_(double);/* reverse polish calculator */main(){char opstr[MAXOP];int type;double lastval = 0.0, op2;while ((type = getop_(opstr)) != EOF) {switch (type) {case NUMBER:push(atof_(opstr));break;case '?':push(lastval);break;case FUNCTION:if (strcmp_(opstr, "sin") == 0) { 判定字母串是否为sinpush(sin_(pop()));break;}else {printf("error: unknown function\n");return 1;}break;case '+':push(pop() + pop());break;case '*':push(pop() * pop());break;case '-':op2 = pop();push(pop() - op2);break;case '/':op2 = pop();if (op2 == 0.0) {printf("error: divided zero\n");return 2;}elsepush(pop() / op2);break;case '\n':printf("\t%g\n", (lastval = pop()));break;default :printf("error: unknown command\n");break;}}printf("\n");return 0;}此处开始getop_函数单元int getch_(void);int ungetch_(int);int isalpha_(int);int tolower_(int);int isdigit_(int);/* getop_(s): get next operating string to s*/int getop_(char s[]){int i, c;while ((s[0] = c = getch_()) == ' ' || c == '\t');if (isalpha_(c)) {s[0] = tolower_(c);for (i = 1; isalpha_(c = getch_()); ++i)s[i] = tolower_(c);s[i] = '\0';if (c != EOF)ungetch_(c);return FUNCTION;}if (!isdigit_(c) && c != '.') {s[1] = '\0';return c;}i = 0;if (isdigit_(c))while (isdigit_(s[++i] = c = getch_()));if (c == '.')while (isdigit_(s[++i] = c = getch_()));s[i] = '\0';if (c != EOF)ungetch_(c);return NUMBER;}此处开始关系紧密、相互协作的两个函数pus和pop的函数单元#define MAXV AL 100double val[MAXV AL];int sp = 0;/*push(x): push x onto value stack */void push(double x){if (sp < MAXV AL)val[sp++] = x;elseprintf("error: stack overflow\n");}/* pop(): pop and return top value from stack*/double pop(void){if (sp > 0)return val[--sp];else {printf("error: stack empty\n");return 0.0;}}此处开始atof_函数单元int isspace_(int);int isdigit_(int);/* atof_(s): convert s to double */double atof_(char s[]){double val, power;int sign, i;for (i = 0; isspace_(s[i]); ++i);sign = (s[i] == '-') ? -1 : 1;if (s[i] == '-' || s[i] == '+')++i;for (val = 0.0; isdigit_(s[i]); ++i)val = val * 10 + s[i] - '0';if (s[i] == '.')++i;for (power = 1.0; isdigit_(s[i]); ++i) {val = val * 10 + s[i] - '0';power *= 10;}return val * sign / power;}此处开始strcmp_函数单元/* strcmp_(s, t): return 0 if s == t, < 0 if s < t, > 0 if s > t*/ int strcmp_(char s[], char t[]){int i;for (i = 0; s[i] == t[i]; ++i)if (s[i] == '\0')return 0;return s[i] - t[i];}此处开始紧密协作的getch_和ungetch_函数单元#define MAXBUF 100char buffer[MAXBUF];int bufp = 0;int getch_(void){return (bufp > 0) ? buffer[--bufp] : getchar();}int ungetch_(int c){if (bufp < MAXBUF)buffer[bufp++] = c;elseprintf("error: too many characters\n");return c;}此处开始sin_函数单元#define ESP 1e-15/* sin_(x): return sin(x) */double sin_(double x){double y, q;int sign, n;y = 0;q = x;sign = 1;n = 1;while (q >= ESP) {y = y + q * sign;q = q * x * x /((n + 1) * (n + 2));n = n + 2;sign = -sign;}return y;}关于sin函数，我们这里使用了sin函数的多项式展开，即sin(x) = x – x3/3! + x5/5! - … + (-1)n-1 x 2n-1/(2n-1)!+…该计算器可以被扩充功能，比如加入cos等其它数学函数，这些函数都存在多项式展开，请同学们查阅相关材料并完成功能扩展。
