我最近做了一个计算器,但只能实现单步运算,对优先级的算法始终没能参悟出来!!
想请教各位大虾帮帮忙!指点一下。
------解决方案--------------------
运算优先级可以通过使用栈Stack来实现,楼主随便找一本数据结构,讲到栈的时候都会讲到运算优先级的实现。
------解决方案--------------------
数据结构上有
用两个栈
一个放运算符
一个放数
我用C语言写的
- C/C++ code
//表达式求值#include <stdio.h>#include <malloc.h>#include <string.h>/**功能:根据运算符计算*参数:a, b参与运算的数, ch运算符*返回值:计算结果,操作符错误则返回0*/int cal(int a, char ch, int b){ switch(ch) { case '+': return a+b; break; case '-': return a-b; break; case '*': return a*b; break; case '/': return a/b; break; } return 0;}/**功能:计算表达式的值(用数组模拟栈)*参数:表达式字符串*返回值:计算结果*/int evaluateExpression(char *str){ int i = 0, result, numSub = 0, operSub = 0; int tmp, len = strlen(str); int *operand = (int*)malloc(sizeof(int)*len); char *operat = (char*)malloc(sizeof(char)*len); while(str[i] != '\0') { switch(str[i]) { case '+': while(operSub > 0 && operat[operSub-1] != '(') { printf("%d %c %d = ", operand[numSub-2], operat[operSub-1], operand[numSub-1]); operand[numSub-2] = cal(operand[numSub-2], operat[operSub-1], operand[numSub-1]); printf("%d\n", operand[numSub-2]); --numSub; --operSub; } operat[operSub++] = '+'; break; case '-': while(operSub > 0 && operat[operSub-1] != '(') { printf("%d %c %d = ", operand[numSub-2], operat[operSub-1], operand[numSub-1]); operand[numSub-2] = cal(operand[numSub-2], operat[operSub-1], operand[numSub-1]); printf("%d\n", operand[numSub-2]); --numSub; --operSub; } operat[operSub++] = '-'; break; case '*': if(str[i+1] >= '0' && str[i+1] <= '9') { tmp = 0; while(str[i+1] >= '0' && str[i+1] <= '9') { tmp = tmp * 10 + str[i+1] - '0'; ++i; } --i; printf("%d * %d = ", operand[numSub-1], tmp); operand[numSub-1] = cal(operand[numSub-1], '*', tmp); printf("%d\n", operand[numSub-1]); ++i; } else operat[operSub++] = '*'; break; case '/': if(str[i+1] >= '0' && str[i+1] <= '9') { tmp = 0; while(str[i+1] >= '0' && str[i+1] <= '9') { tmp = tmp * 10 + str[i+1] - '0'; ++i; } --i; printf("%d / %d = ", operand[numSub-1], tmp); operand[numSub-1] = cal(operand[numSub-1], '/', tmp); printf("%d\n", operand[numSub-1]); ++i; } else operat[operSub++] = '/'; break; case '(': operat[operSub++] = '('; break; case ')': while(operat[operSub-1] != '(') { printf("%d %c %d = ", operand[numSub-2], operat[operSub-1], operand[numSub-1]); operand[numSub-2] = cal(operand[numSub-2], operat[operSub-1], operand[numSub-1]); printf("%d\n", operand[numSub-2]); --numSub; --operSub; } --operSub; break; default: tmp = 0; while(str[i] >= '0' && str[i] <= '9') { tmp = tmp * 10 + str[i] - '0'; ++i; } --i; operand[numSub++] = tmp; break; } ++i; } while(numSub > 1 && operSub >= 1) { printf("%d %c %d = ", operand[numSub-2], operat[operSub-1], operand[numSub-1]); operand[numSub-2] = cal(operand[numSub-2], operat[operSub-1], operand[numSub-1]); printf("%d\n", operand[numSub-2]); --numSub; --operSub; } result = operand[numSub-1]; free(operand); free(operat); return result;}int main(){ char *str = "225/15-20+(4-3)*2"; int result; printf("计算过程:\n"); result = evaluateExpression(str); printf("计算结果:result = %d\n", result); return 0;}计算过程:225 / 15 = 1515 - 20 = -54 - 3 = 11 * 2 = 2-5 + 2 = -3计算结果:result = -3