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

[labfans]

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰结构由弗里德里希·鲍尔（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 /”；数字的数位写法也是常规顺序。


伪代码

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

c语言实现代码：

#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;
}