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 }
标签：shuchu,vIndex,++,C语言,shuru,scIndex,算法,波兰,opIndex From： https://www.cnblogs.com/pengpai/p/17947886