Reverse Polish Calculator （逆波兰计算器）方案的分析——如何解决问题，从需要到实现
Reverse Polish Calculator （逆波兰计算器）方案的分析——如何解决问题，从需要到实现
注：文章素材来源于K&R第二版
需要实现的功能：
（针对用户的期望）
1、基本的四则运算
2、取模运算
*3、其它数学函数的运算。比如三角函数、幂函数、指数函数等
*4、能够调用上一步的结果（待补充）
用户可能的行为：
用户可能的输入（用□代表空格，其它不可见字符使用其转义字符表示）
正常输入：
3□2□-\n
3.5□2.1□*\n (带有小数点)
-0.5□-3□/\n (带有负数)
多余空格：□□\t3□2-□\n
小数点前不带整数：-.5□-.6□+\n
用户期待的结果：
能够进行多种数学运算，包括小数和负数的运算，三角函数等；
输入回车符后能立即得到正确答案，得到答案后程序不会退出，可以继续计算其他算术式，直到用户输入EOF，结束计算器的运行。
整体框架
while (下一个运算符或者操作数不是EOF )
if (是数 )
将数压入栈中
else if (是运算符 )
弹出所需数目的操作数
执行运算
将结果压入栈中
else if (是换行符 )
弹出并打印栈顶值
else
出错
1/*
2 *逆波兰计算器主函数
3 */
4
5/*
6 *算法描述：
7 * while (下一个运算符或者操作数不是EOF )
8 * if (是数 )
9 * 将数压入栈中
10 * else if (是运算符 )
11 * 弹出所需数目的操作数
12 * 执行运算
13 * 将结果压入栈中
14 * else if (是换行符 )
15 * 弹出并打印栈顶值
16 * else
17 * 出错
18 */
19#include <stdio.h>
20#include <stdlib.h>
21#include <math.h> //使用fmod()函数和其他数学函数
22#include <string.h> //使用strcmp()函数
23
24#define MAXOP 100
25#define NUMBER'0'
26#define NAME'f'
27
28intgetop(char s[] );
29voidpush(double);
30doublepop(void);
31voidmathfunc(char s[] );
32
33intmain(void)
34{
35 int type;
36 double op2;
37 char s[MAXOP];
38
39 while( (type=getop(s)) != EOF )
40 {
41 switch( type)
42 {
43 case NUMBER:
44 push(atof( s) );
45 break;
46 case'+':
47 push(pop() +pop() );
48 break;
49 case'*':
50 push(pop() *pop() );
51 break;
52 case'-':
53 op2=pop();
54 push(pop() - op2);
55 break;
56 case'/':
57 op2=pop();
58 if( op2!=0.0)
59 push(pop() / op2);
60 else
61 printf("Error : zero divisor\n");
62 break;
63 /*
64 *增加取模运算
65 */
66 case'%':
67 op2=pop();
68 if( op2!=0.0)
69 push(fmod(pop() , op2) );
70 else
71 printf("Error : zero divisor\n");
72 break;
73 /*
74 *增加其他数学函数
75 */
76 case NAME:
77 mathfunc( s);
78 break;
79
80 case'\n':
81 printf("\t%.8g\n",pop() );
82 break;
83 default:
84 printf("error: unknown command %s\n", s );
85 break;
86 }
87 }
88 return0;
89}
90
91
92voidmathfunc(char s[] )
93{
94 double op2;
95
96 if(strcmp( s,"sin") ==0)
97 push(sin(pop() ) );
98 else if(strcmp( s,"cos") ==0)
99 push(cos(pop() ) );
100 else if(strcmp( s,"exp") ==0)
101 push(exp(pop() ) );
102 else if(strcmp( s,"pow") ==0)
103 {
104 op2=pop();
105 push(pow(pop(), op2) );
106 }
107 else
108 printf("error: %s not supported\n", s );
109}
如何获取操作数或者运算符（针对用户的行为）
1、获取操作符：基本的四则运算符是单个的字符，直接读入字符。
2、获取操作数：操作数是一系列数字值或者小数点符号或者负号。
3、获取输入结束符：根据用户需求，在读取一个换行符后结束输入，输出结果。
4、对错误输入的处理：读入数字字符和正常的运算符不会产生错误，对于非法的字符，直接读入，交由主函数处理。
具体获取方法：
1、由于针对操作数和运算符读取的方式不一样，操作数需要一个数组来存放一系列字符，而运算符只需要一个字符变量来存放即可，所以读取时需要进行两种类型变量的数据交换，字符变量使用返回值进行交换，字符串可以在函数中进行修改来实现数据交换。由此我们大致可以知道获取操作数和运算符的函数原型：
int getop ( char s[] );
函数返回int型值（实际为char，为了处理EOF所以为int），把一个字符数组作为函数的参数，存储读到的操作数；
2、以具体输入为例进行分析
□3.5□2.1□*\n
在这个输入中，我们希望得到两个操作数3.5、2.1和一个运算符*以及一个结束符\n
2.1、首先处理第一个前面的（如果有的话）和关键字符之间的空白（□或者\t）：采取的方法是跳过（连续读取，直至出现第一个不是空白的字符）空白。（空白还有一个作用就是区分负号和减号，在后面会具体谈及。）由于第一个字符可能是操作数的起始部分，而且空白的结束是以读取到下一个不是空白的字符为结束的，这个非空白的字符有可能就是操作数的一部分，所以还是应该将读取的字符存入数组。
2.2、在处理完空白之后，要及时将字符数组变为字符串，以免在其它函数使用时出错。
2.3、如果第一个非空字符不是操作数的组成部分（digit、'.'、'-'），就把这个字符返回。
2.4、如果这个字符是操作数的组成部分就“激活”字符数组，继续读取操作数的剩余部分并存入数组中，直到读到下一个不能组成操作数的字符，将字符数组转换为字符串。
2.5、处理最后读取的字符，如果它是EOF直接丢弃，否则就把它重新放入输入流，供下一次读取。
此时又引发一个问题，就是输入缓存，需要建立一个缓冲区，可以将“误读”的字符重新放到这个缓冲区内，供下一次读取。（稍后详谈）
2.6、正确读取到操作数后，函数需要一个返回值，由之前的假定，它不能是数组，只能是字符常量，但这个字符常量的值并无实际用途，所以只需要一个标签即可，我们把它设置为NUMBER '0'
3、负号和减号的区分
当读入的字符是'-'时，如果下一个字符是数字或者小数点，那么这个'-'就是负号，否则就是减号。
4、对数学函数的读取
当读入的是一个小写字母时，继续读入小写字母（如果后面有的话），并存入数组，形成字符串，将最后读入的一个不是小写字母的字符（不是EOF）放入输入中，判断字符串的长度，小于1就将读入的一个字符返回，否则就返回一个标志，表示已经读取到函数字符串，并在主程序中使用这种字符串。
1/*
2 *获取操作符或者操作数的函数
3 */
4#include <stdio.h>
5#include <ctype.h>
6#include <string.h>
7
8#define NUMBER'0'
9#define NAME'f'
10
11intgetch(void);
12intungetch(int c);
13
14intgetop(char s[] )
15{
16 int i, c;
17 while( (s[0] = c =getch() ) ==' ' || c=='\t')
18 ;
19 s[1] = '\0';
20 i=0;
21
22 /*
23 *增加对其他函数字符串的读取
24 */
25
26 if(islower( c) )
27 {
28 while(islower( s[++i] = c =getch() ) )
29 ;
30 s[i] = '\0';
31 if( c!= EOF)
32 ungetch( c);
33 if(strlen( s) >1)
34 return NAME;
35 else
36 return c;
37 }
38
39 if( !isdigit( c) && c!='.' && c!='-')
40 return c;
41
42 /*
43 *增加对负号和减号的区分
44 */
45 if( c=='-')
46 if(isdigit( c=getch() ) || c=='.')
47 s[++i] = c;
48 else
49 {
50 if( c!= EOF)
51 ungetch( c);
52 return'-';
53 }
54
55 if(isdigit( c) )
56 while(isdigit( s[++i] = c =getch() ) )
57 ;
58 if( c=='.')
59 while(isdigit( s[++i] = c =getch() ) )
60 ;
61
62 s[i] ='\0';
63
64 if( c!= EOF)
65 ungetch( c);
66
67 return NUMBER;
68}
如何实现栈（数据的组织）
我们把操作数都放到一个数组中，只要程序遇到操作符，就会将相应个数的操作数取出来，进行运算，然后将结果再次放入数组中。这种基于数组的“操作方式”（栈，实际上就是数组或者链表等，由于对其操作方式的不同，就会产生栈、列队等各种数据结构）就是栈。
它起码应该具备两个基本功能：进栈和出栈。
我们需要一个数组来存储数据，还要一个位置量来标记栈顶位置，方便进出栈。
1/*
2 *用于栈的操作函数
3 */
4#include <stdio.h>
5#define MAXVAL 100
6
7int sp=0;
8double val[MAXVAL];
9
10voidpush(double f)
11{
12 if( sp< MAXVAL)
13 val[sp++] = f;
14 else
15 printf("error: stack full\n");
16}
17
18doublepop(void)
19{
20 if( sp>0)
21 return val[--sp];
22 else
23 {
24 printf("error: empty stack\n");
25 return0.0;
26 }
27}
如何实现输入缓存
我们需要一个栈（存取都发生在数组的同一端），当发生“误读”时，就将这个字符推进栈中，下一次读取时，如果栈不是空，就读取栈顶元素，否则就从标准输入读取。
1/*
2 *读取字符和放入被读取字符的函数
3 */
4#include <stdio.h>
5#define BUFSIZE 100
6
7char buf[BUFSIZE];
8int bufp=0;
9
10intgetch(void)
11{
12 return( bufp>0) ? buf[--bufp] :getchar();
13}
14
15voidungetch(int c)
16{
17 if( bufp>= BUFSIZE)
18 printf("ungetch: too many characters\n");
19 else
20 buf[ bufp++ ] = c;
21}
/* * 读取字符和放入被读取字符的函数 */#include <stdio.h>#define BUFSIZE 100char buf[BUFSIZE];int bufp = 0;int getch ( void ){return ( bufp > 0 ) ? buf[--bufp] : getchar();}void ungetch ( int c ){if ( bufp >= BUFSIZE )printf ( "ungetch: too many characters\n" );elsebuf [ bufp++ ] = c;}