C/C++|简单表达式求值——算符优先法 C

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

题目描述：读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。输入：测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。样例输入： 1 + 2 4 + 2 * 5 - 7 / 11 0 样例输出： 3.00 13.36

思路对表达式 4 + 2 × 5- 7 / 11进行计算，需要了解算法四则运算的规则，即：

先乘除，后加减
从左到右计算

实现算法

为了实现算符优先法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符; 另一个称为OPRD，用以寄存操作数或者运算结果。
初始化两个栈，并且置栈空。（假设表达式是没有语法错误的）
依次读入表达式中每个字符，若是操作数则进OPTD栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即表达式指针到了最后一个字符并且OPTR栈为空）

【C/C++|简单表达式求值——算符优先法】

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

#include #include #include #define stacksize 201struct optr { char operator[stacksize]; int top; }; struct optd { double data[stacksize]; int top; }; 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); } optr->top = optd->top = 0; //计算表达式的值，使用“算符优先法” 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 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优先级高返回0 int 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; } }