容易表达式求值——算符优先法

简单表达式求值——算符优先法
前言周五加班的时候，在九度oj上练习了一道简单表达式求值的题目，用到了“算符优先法”，这里简单的记录一下
题目

题目描述：

    读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入：

    测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出：

    对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入：

1 + 24 + 2 * 5 - 7 / 110

样例输出：

3.0013.36

思路对表达式 4 + 2 × 5  - 7 / 11进行计算，需要了解算法四则运算的规则，即：1.先乘除，后加减2.从左到右计算实现算法（1）为了实现算符优先法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符;另一个称为OPRD，用以寄存操作数或者运算结果。（2）初始化两个栈，并且置栈空。（假设表达式是没有语法错误的）（3）依次读入表达式中每个字符，若是操作数则进OPTD栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即表达式指针到了最后一个字符并且OPTR栈为空）

代码实现（c语言顺序栈）

#include <stdio.h>#include <stdlib.h>#include <string.h>#define stacksize 201struct optr{char operator[stacksize];int top;};struct optd{double data[stacksize];int top;};void initStackOptr(struct optr *);void initStackOptd(struct optd *);void pushStackOptr(struct optr *, char );void pushStackOptd(struct optd *, double );char getStackOptrTop(struct optr *);int compareOperator(char, char);char popStackOptr(struct optr *);double popStackOptd(struct optd *);double calculateData(double, double, char);int main(){struct optr *optr;struct optd *optd;int i, len;double sum, x, data1, data2;char string[201], opt, opt1, opt2;while(gets(string) && string[0] != '0'){//初始化栈、表达式长度len = strlen(string);optr = (struct optr *)malloc(sizeof(struct optr));optd = (struct optd *)malloc(sizeof(struct optd));if(optr == NULL || optd == NULL){exit(EXIT_FAILURE);}initStackOptr(optr);initStackOptd(optd);//计算表达式的值，使用“算符优先法”for(i = 0; i < len; i ++){if(string[i] != ' '){if(string[i] >= '0' && string[i] <= '9'){x = string[i] - '0';while(string[i + 1] >= '0' && string[i + 1] <= '9'){x = 10 * x + (string[i + 1] - '0');i ++;}//操作数进栈pushStackOptd(optd, x);}else{//获取栈顶运算符opt = getStackOptrTop(optr);switch(compareOperator(opt, string[i])){case 0://栈顶优先级低pushStackOptr(optr, string[i]);break;case 1://栈顶优先级高opt = popStackOptr(optr);data1 = popStackOptd(optd);data2 = popStackOptd(optd);sum = calculateData(data1, data2, opt);pushStackOptd(optd, sum);i --;break;}}}}//判断算符栈是否为空while(optr -> top != 0){opt = popStackOptr(optr);data1 = popStackOptd(optd);data2 = popStackOptd(optd);sum = calculateData(data1, data2, opt);pushStackOptd(optd, sum);}//输出计算结果printf("%.2lf\n",sum);}return 0;}void initStackOptr(struct optr *s){s->top == 0;}void initStackOptd(struct optd *s){s->top == 0;}void pushStackOptr(struct optr *s, char opt){//判断栈满if(s->top - 1 == stacksize){exit(EXIT_FAILURE);}s->operator[s->top ++] = opt;}void pushStackOptd(struct optd *s, double x){//判断栈满if(s->top - 1 == stacksize){exit(EXIT_FAILURE);}s->data[s->top ++] = x;}char getStackOptrTop(struct optr *s){//判断栈空if(s->top == 0){return '#';}return s->operator[s->top - 1];}int compareOperator(char opt1, char opt2){//默认opt1优先级高，opt2优先级高返回0int flag = 1;if(((opt1 == '+' || opt1 == '-') && (opt2 == '*' || opt2 == '/')) || opt1 == '#'){flag = 0;}return flag;}char popStackOptr(struct optr *s){//判断栈空if(s->top == 0){exit(EXIT_FAILURE);}return s->operator[-- s->top];}double popStackOptd(struct optd *s){//判断栈空if(s->top == 0){exit(EXIT_FAILURE);}return s->data[-- s->top];}double calculateData(double data1, double data2, char operator){switch(operator){case '+':return data2 + data1;case '-':return data2 - data1;case '*':return data2 * data1;case '/':if(data1 == 0){exit(EXIT_FAILURE);}return data2 / data1;}}

大家可以参考一下，好了，下一篇博客可能就是openvpn的搭建了，有需要的同学可以关注，工作需要记录一下搭建过程吧

查看更多 下一篇