1 #include <stdio.h> 2 3 //数字模式识别 4 #define IS_NUM(c) (((c)>='0') && ((c)<='9') || ((c)=='.')) 5 //符号字符识别 6 #define IS_OPERATOR(c) (((c)=='+') || ((c)=='-') || ((c)=='*') || ((c)=='/') || ((c)=='(')) 7 //加减符号识别 8 #define IS_AS(c) (((c)=='+') || ((c)=='-')) 9 //乘除符号识别 10 #define IS_MD(c) (((c)=='*') || ((c)=='/')) 11 12 13 //逆波兰式 识别原则 14 //1、遇见数字直接压入输出数组里边； 15 //2、遇见乘除符号，则先把前边紧跟着的所有乘除符号逆序弹出到输出数组中 ，然后把当前的符号压入符号栈； 16 //3、遇见加减号，则把最近前括号“(”之后的的所有符号全部弹出到输出数组中，然后压入当前符号； 17 //4、每次遇见任何符号，都表明之前的数据识别完成，这里需要添加空格用来区分两个数据 18 //5、如果算式刚开始或者其他符号之后出现“-”，这这个符号会被识别成符号， 19 // 负数标志位置1，先在输出数组中压入0和空格，且在后边数据识别完成之后，直接添加“-”，用0-x的方式实现负数 20 //6、如果遇见前括号“(” 则直接压入符号栈；如果遇见后括号“)”，则把最近的前括号之后所有的符号逆序弹出到输出数组； 21 //7、原式子识别完成之后，如果符号栈还有数据，则按照逆序分别弹出到输出数组中； 22 //缺陷：没有进行括号匹配识别，也没有处理连续两个符号重新一块输入的bug，还有一个数据输入多个小数点的bug！！！！！ 23 24 //例如 1.2+-42.8/2*(1*-2.56/(3-4))*(10/5+2.6) 25 //a、根据原则1和原则3和原则4，输出数组：1.2（空格），符号栈：+ 26 //b、根据原则5、1、2，输出数组 1.2 0 42.8 - 2 符号栈：+ / 27 //c、根据原则2，输出数组：1.2 0 42.8 - 2 / 符号栈：+ * 28 //d、根据原则6，输出数组：1.2 0 42.8 - 2 / 符号栈：+ * ( 29 //e、根据原则1、2、3、4、5、6 输出数组：1.2 0 42.8 -2 /1 0 2.56 -* 符号栈：+ * (/( 30 //f、根据原则1、3 输出数组：1.2 0 42.8 -2 /1 0 2.56 -*3 4 - 符号栈：+ * (/( 31 //g、根据原则6 输出数组：1.2 0 42.8 -2 /1 0 2.56 -*3 4 -/ 符号栈：+ * 32 //h、之前的原则，则后续结果1.2 0 42.8 -2 /1 0 2.56 -*3 4 -/*10 5 /2.6 +*+ 33 void RPN(char shuru[],char shuchu[]) { 34 char i; 35 char scIndex = 0; //输出栈顶索引 36 char opera[20] = {0}; //符号栈 37 char opIndex = 0; //符号栈顶索引 38 char fushu = 0; //负数标志位 39 char errNum = OK; //返回错误置 40 41 for(i=0;shuru[i]!='\0';i++) { 42 if(IS_NUM(shuru[i])) { //数据字符 43 shuchu[scIndex++] = shuru[i]; //把数组直接输出 44 } else if(IS_MD(shuru[i])) { //乘除字符 45 if(IS_NUM(shuchu[scIndex-1])) { //添加空格来区分数据，如果是负数模式，则添加负号，下同 46 shuchu[scIndex++] = ' '; //添加数据分割的空格 47 if(fushu==1) { //负数模式 48 shuchu[scIndex++] = '-';//把符号添加到结果中 49 fushu=0; //负数标志位清零 50 } 51 } 52 //如果是上一个字符是乘除则一个一个弹出来填充到结果中， 53 //直到符号栈没有符号，或者遇见前括号“(” 54 while(IS_MD(opera[opIndex-1]) && (opIndex>0) ) {//&& (opera[opIndex-1]!='(') 55 shuchu[scIndex++] = opera[--opIndex]; 56 } 57 opera[opIndex++] = shuru[i]; //填充当前符号到符号栈 58 } else if(IS_AS(shuru[i])) { //如果是加减模式 59 if(IS_NUM(shuchu[scIndex-1])) { //添加空格，区分负号，同上 60 shuchu[scIndex++] = ' '; 61 if(fushu==1) { 62 shuchu[scIndex++] = '-'; 63 fushu=0; 64 } 65 } 66 //如果算式刚开始就是“-”，或者其他符号紧跟着“-”则这个减号起到负数所用 67 if((shuru[i]=='-') && ((scIndex==0) || (IS_OPERATOR(shuru[i-1])))) { 68 shuchu[scIndex++] = '0'; //先添加0 把负数处理成0-x的模式 69 shuchu[scIndex++] = ' '; 70 fushu=1; //负数标志位 71 } else { 72 while((opIndex>0) && (opera[opIndex-1]!='(')) {//把前括号之前的符号全部弹出 73 shuchu[scIndex++] = opera[--opIndex]; 74 } 75 opera[opIndex++] = shuru[i];//压入当前符号 76 } 77 78 } else if(shuru[i]=='(') { //如果是前括号 则直接压入括号 79 if(IS_NUM(shuchu[scIndex-1])) { //添加空格，区分负号，同上 80 shuchu[scIndex++] = ' '; 81 if(fushu==1) { 82 shuchu[scIndex++] = '-'; 83 fushu=0; 84 } 85 } 86 opera[opIndex++] = shuru[i]; //压入前括号 87 } else if(shuru[i]==')') { //如果是后括号，则直接弹出前括号后边的所有符号 88 if(IS_NUM(shuchu[scIndex-1])) { 89 shuchu[scIndex++] = ' '; 90 if(fushu==1) { 91 shuchu[scIndex++] = '-'; 92 fushu=0; 93 } 94 } 95 while(opera[opIndex-1]!='(') { //弹出前括号之后的所有符号 96 shuchu[scIndex++] = opera[--opIndex]; 97 } 98 opIndex--; //栈顶减1，剔除前括号 99 } 100 } 101 //puts(shuchu); 102 while((opIndex>0)) { //如果循环之后符号栈还有数据，则逆序弹出 103 shuchu[scIndex++] = opera[--opIndex]; 104 } 105 } 106 107 //根据逆波兰式计算数据原则 108 //1、遇见数据进行数字识别，注意识别的时候有整数和小数模式，遇见空格，表明当前数据识别完成，识别完成的数据压入数据栈 ； 109 //2、如果遇见符号，则按照顺序弹出两个数据，然后这两个数据按照顺序进行符号匹配的运算，结果压入数据栈； 110 //3、所有数据计算完成之后，数据栈就留下唯一结果，就是最终结果 111 //例如上边逆波兰式 1.2 0 42.8 -2 /1 0 2.56 -*3 4 -/*10 5 /2.6 +*+ 112 //a、先压入1.2 0 42.8 ，当看见符号，则弹出42.8和0 ，然后计算0-42.8，把结果压入数据栈，1.2 -42.8 113 //b、然后出现2，则先把2压入数据栈； 114 //c、遇见/，则弹出2和-42.8，计算-42.8/2结果为-21.4压入数据栈，结果为1.2 -21.4 115 //d、后边的数据以此类推 116 float RPNOperation (char shuru[]) { 117 char i; 118 float value[10]={0}; //数据和计算数据的栈 119 char vIndex=0; //数据栈顶索引 120 char xs=0; //小数标志位 121 float xishu=0.1; //小数系数 122 float s0,s1; //运算数据变量 123 124 125 for(i=0;shuru[i] != '\0';i++) { //遍历所有逆波兰式字符串 126 if(IS_NUM(shuru[i])) { //数字模式 127 if(shuru[i]=='.') { //如果判断小数点，则小数标志位置1 128 xs=1; 129 } else { //纯数字模式，则计算数据 130 if(xs==0) { //整数模式计算方法，a=a*10+b，其中a是上一次数据，b是当前数据 131 value[vIndex] = value[vIndex]*10 + (shuru[i]-'0'); 132 } else if(xs==1){ //如果是小数模式，则每一个新数据都要倍一个小数系数 133 value[vIndex] += xishu*(shuru[i]-'0'); 134 xishu/=10; //小数系数缩小到原来的十分之一，供下次使用 135 } 136 } 137 } else if(shuru[i]==' ') { //如果是空格，则表明上边的数据已经完结 138 xs=0; //小数标志位清零 139 vIndex++; //数据栈加1 140 xishu=0.1; //小数系数恢复到0.1 141 } else if(IS_OPERATOR(shuru[i])) { //如果遇见符号 142 s0=value[--vIndex]; //弹出第一数据 143 value[vIndex] = 0; //原数据必须清零，否则，影响下一次数据识别 144 s1=value[--vIndex]; //弹出第二个数据 145 switch (shuru[i]){ //根据符号进行计算 146 case '+':value[vIndex]=s1+s0;break; 147 case '-':value[vIndex]=s1-s0;break; 148 case '*':value[vIndex]=s1*s0;break; 149 case '/':value[vIndex]=s1/s0;break; 150 } 151 vIndex++; 152 xs=0; 153 xishu=0.1; 154 } 155 } 156 return value[0]; //运算完成之后，栈里边只留下最终结果 157 } 158 159 main() { 160 //带带括号嵌套，带负数的运算式 161 char shuru[]="1.2+-42.8/2*(1*-2.56/(3-4))*(10/5+2.6)"; 162 //逆波兰式输出数组 163 char shuchu[35]={0}; 164 float v; //最终结果 165 RPN(shuru,shuchu); //计算逆波兰式 166 puts(shuchu); //打印逆波兰式 167 v=RPNOperation(shuchu); //计算数据结果 168 printf("%f",v); //打印结果 169 }