逆波兰表示法和用c语言实现的简易计算器
 

[B]逆波兰表示法[/B]（[B]Reverse Polish notation[/B]，[B]RPN[/B]，或[B]逆波兰记法[/B]），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为[B]后缀表示法[/B]。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林（Charles Hamblin）在1960年代中期扩充[1][2]
在1960和1970年代，逆波兰记法广泛地被用于台式计算器，因此也在普通公众（工程、商业和金融领域）中使用。
下面大部分是关于二元运算，一个一元运算使用逆波兰记法的例子是阶乘的记法。


逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“3 4 +”，而不是“3 + 4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”：先3减去4，再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 * 5”与“(3 - 4)*5”不相同，但后缀记法中前者写做“3 4 5 * -”，无歧义地表示“3 (4 5 *) −”；后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，和能很快求值。
注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”；数字的数位写法也是常规顺序。


[B]伪代码[/B]

[LIST][*]while 有输入符号[LIST][*]读入下一个符号[*]IF 是一个操作数[LIST][*]入栈[/LIST] [*]ELSE IF 是一个操作符[LIST][*]有一个先验的表格给出该操作符需要n个参数[*]IF 堆栈中少于n个操作数[LIST][*][B](错误)[/B] 用户没有输入足够的操作数[/LIST] [*]Else，n个操作数出栈[*]计算操作符。[*]将计算所得的值入栈[/LIST] [/LIST] [*]IF 栈内只有一个值[LIST][*]这个值就是整个计算式的结果[/LIST] [*]ELSE 多于一个值[LIST][*][B](错误)[/B] 用户输入了多余的操作数[/LIST][/LIST]c语言实现代码：

[CODE]#include <stdio.h>
#include <stdlib.h> /*为了使用atof()函数 */
#include <ctype.h>

#define MAXOP 100 /*操作数或运算符的最大长度 */
#define NUMBER '0' /*标识找到一个数 */

int getop(char []);
void push(double);
double pop(void);


/* 逆波兰计算器 */
main()
{
int type;
double op2;
char s[MAXOP];

while ((type = getop(s)) != EOF) {
switch (type){
case NUMBER:
push(atof(s));
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)
push(pop() / op2);
else
printf("error: zero divesor\n");
break;
case '%':
op2 = pop();
if (op2 != 0.0)
push(fmod(pop(),op2));
else
printf("error: zero divesor\n");
break;
case '\n':
printf("\t%.8g\n",pop());
break;
default:
printf("error: unknown command %s\n",s);
break;
}
}
return 0;
}


#define MAXVAL 100 /* 栈val的最大深度 */

int sp = 0; /* 下一个空闲栈位置 */
double val[MAXVAL]; /* 值栈 */

/* push函数：把f压入到值栈中 */
void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full,can't push %g\n",f);
}

/* pop函数：弹出并返回栈顶的值 */
double pop(void)
{
if(sp > 0)
return val[--sp];
else {
printf("error: stack empty\n");
return 0.0;
}
}


int getch(void);
void ungetch(int);

/* getop函数：获取下一个运算符或数值操作数 */
int getop(char s[])
{
int i,c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
i = 0;
if (!isdigit(c) && c != '.' && c != '-')
return c; /* 不是数 */
if (c == '-')
if (isdigit(c = getch()) || c == '.')
s[++i] = c; /* 负数 */
else {
if (c != EOF)
ungetch(c);
return '-'; /* 减号 */
}
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;
}



#define BUFSIZE 100

char buf[BUFSIZE]; /* 用于ungetch函数的缓冲区 */
int bufp = 0; /* buf中下一个空闲位置 */

int getch(void) /* 取一个字符（可能压回的字符） */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* 把字符压回到输入中 */
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}[/CODE]