中转后 具体转换方式:
1.从左到右遍历需要计算的字符串
2.若是运算数,直接压入后缀表达式栈
3.若是左括号,直接压入运算符栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈)
4.若是右括号,(意味着括号已结束)不断弹出运算符栈顶运算符并输出到后缀表达式栈
直到遇到左括号(弹出但不输出)
5.运算符,将该运算符与运算符栈顶运算符进行比较,
如果优先级高于栈顶运算符则压入运算符栈(该部分运算还不能进行),
如果优先级低于等于栈顶运算符则将栈顶运算符弹出到后缀表达式栈然后比较新的栈顶运算符.
(低于弹出意味着前面部分可以运算,先输出到后缀表达式栈一定是高优先级运算符,
等于弹出是因为同等优先级,从左到右运算)
直到优先级大于栈顶运算符或者栈空,再将该运算符入运算符栈
6.如果字符串处理完毕,则按顺序从运算符栈弹出所有运算符到后缀表达式栈
使用后缀表达式计算的方法：
1、 按顺序取后缀表达式的每个值
2、 若是数字 则入栈
3、 若是操作符 则从栈取出两个数字 进行运算 运算之后再将结果入栈
4、 循环上述过程知道后缀表达式结束 栈顶元素（栈中只有一个元素）即为结果
1 #include <windows.h> 2 #include <stdio.h> 3 #include <string.h> 4 #include <malloc.h> 5 #define NUM 0 6 #define OPERATION 1 7 typedef struct {//栈中的结点 8 int val; 9 int type; 10 } Node; 11 typedef struct {//栈 12 const char* name;//栈名 13 Node* sta;//结点 14 int size;//最多存储多少个元素 15 int cnt;//当前存储了多少个元素 16 } MyStack; 17 void trace(MyStack* s)//栈的遍历 18 { 19 int i; 20 printf("%s栈中的元素为：", s->name); 21 for (i = 0; i < s->cnt; i++) { 22 if (s->sta[i].type == NUM) {//若是数字 23 printf("%d ", s->sta[i].val); 24 } 25 else {//若是字符 26 printf("%c ", (char)s->sta[i].val); 27 } 28 } 29 printf(" "); 30 } 31 void sFree(MyStack* s)//释放栈 32 { 33 if (s->sta != NULL) { 34 free(s->sta); 35 s->sta = NULL; 36 } 37 return; 38 } 39 int sInit(MyStack* s, const char* name, int size)//初始化栈 40 { 41 s->name = name; 42 s->size = size; 43 s->sta = (Node*)calloc(s->size, sizeof(Node));//calloc申请后 其中存的都是0 44 if (s->sta == NULL) { 45 return -1;//分配失败 46 } 47 s->cnt = 0;//当前栈中元素有0个 48 return 0;//分配成功 49 } 50 void sPush(MyStack* s, Node item)//入栈一个元素 51 { 52 if (s->cnt == s->size) { 53 printf("栈空间不足 "); 54 return; 55 } 56 s->sta[s->cnt] = item; 57 s->cnt++; 58 return; 59 } 60 bool sIsEmpty(MyStack* s)//判断栈是否为空 61 { 62 return s->cnt == 0; 63 } 64 void sPop(MyStack* s, Node* item)//删除栈顶元素 并返回值到item 65 { 66 if (sIsEmpty(s)) { 67 return; 68 } 69 *item = s->sta[s->cnt - 1]; 70 s->cnt--; 71 return; 72 } 73 void sTop(MyStack* s, Node* item)//获得栈顶元素到item 不删除栈顶袁术 74 { 75 if (sIsEmpty(s)) { 76 return; 77 } 78 *item = s->sta[s->cnt - 1]; 79 return; 80 } 81 bool myIsNum(char ch)//判断是否是数字 82 { 83 return ch >= '0' && ch <= '9'; 84 } 85 bool myIsOper(char ch)//判断是否是运算符 86 { 87 return ch == '+' || ch == '-' || ch == '*' || ch == '/'||ch=='('||ch==')'; 88 } 89 //处理数值 90 void procNum(MyStack* postfix_expression, char* s, int len, int* pi) 91 { 92 int i = *pi;//令i等于当前在处理的元素的坐标 93 int num=0;//当前数字的值 具体是多少 94 Node item_num; 95 while (myIsNum(s[i])) 96 { 97 num = num * 10 + s[i]-'0'; 98 i++; 99 } 100 //新建结点 101 item_num.type = NUM; 102 item_num.val = num; 103 //数字直接入后缀表达式的栈 104 sPush(postfix_expression, item_num); 105 *pi = i-1;//改变calculate_postfix_expression 中i的值 106 return; 107 } 108 //处理运算符 109 void procOper(MyStack* postfix_expression, MyStack* s_oper, char* s, int len, int* pi) 110 { 111 int i = *pi; 112 Node item; 113 Node top_item; 114 Node pop_item; 115 if (s[i] == '(')//如果是( 直接存入运算符栈 116 { 117 item.type = OPERATION; 118 item.val = s[i]; 119 sPush(s_oper, item); 120 } 121 else if (s[i] == ')')//若是) 则弹出到(为止 122 { 123 int flag = 0;//是否找到了 ( 124 while (!sIsEmpty(s_oper)) { 125 sPop(s_oper, &pop_item); 126 if (pop_item.val == '(') {//若找到了左括号退出 127 flag = 1; 128 break; 129 } 130 sPush(postfix_expression, pop_item);//若未找到左括号 则一直从运算符栈中pop 131 } 132 if (!flag) 133 { 134 printf("括号不匹配！"); 135 exit(0); 136 } 137 } 138 //如果是乘除 139 else if (s[i] == '*' || s[i] == '/') 140 { 141 item.type = OPERATION; 142 item.val = s[i]; 143 while (!sIsEmpty(s_oper)) { 144 sTop(s_oper, &top_item); 145 //如果当前运算符栈的栈顶是+ - ( 146 //则* /级别较高 则跳出循环 147 if (top_item.val == '+' || top_item.val == '-' || top_item.val == '(') { 148 break; 149 } 150 //若当前运算符栈顶不是+ - ( 则是* / 151 //则需先把* / pop完 152 sPop(s_oper, &pop_item); 153 sPush(postfix_expression, pop_item); 154 } 155 //才能将当* /入栈 156 sPush(s_oper, item); 157 } 158 //如果是 + - 159 else if (s[i] == '+' || s[i] == '-') 160 { 161 item.type = OPERATION; 162 item.val = s[i]; 163 while (!sIsEmpty(s_oper)) { 164 sTop(s_oper, &top_item); 165 //如果当前运算符栈的栈顶是 ( 166 //则当前运算符级别较高 则跳出循环 167 if (top_item.val == '(') { 168 break; 169 } 170 //若当前运算符栈顶不是 ( 则是+ - * / 171 //则需先把+ - * /pop完 172 sPop(s_oper, &pop_item); 173 sPush(postfix_expression, pop_item); 174 } 175 //才能将当+ - 入栈 176 sPush(s_oper, item); 177 } 178 else 179 { 180 printf("输入了非空格 非数字 非运算符的元素 %c ", s[i]); 181 exit(0); 182 } 183 return; 184 } 185 //计算后缀表达式 存储在s_trans中 186 void calculate_postfix_expression(MyStack* postfix_expression, MyStack* s_oper, char* s, int len) 187 { 188 int i; 189 int ret; 190 int num; 191 Node item; 192 for (i = 0; i < len; i++) { 193 if (s[i] == ' ') {//当前输入为空格时 跳过 194 continue; 195 } 196 if (myIsNum(s[i])) {//当前是数字时 197 procNum(postfix_expression, s, len, &i); 198 continue; 199 } 200 if (myIsOper(s[i])) {//当前是运算符时 进入运算的处理程序 201 procOper(postfix_expression, s_oper, s, len, &i); 202 continue; 203 } 204 printf("输入了非空格 非数字 非运算符的元素 %c ", s[i]); 205 exit(0); 206 } 207 //若运算栈不为空 依次pop出运算栈中的元素 再push到后缀表达式栈 208 while (!sIsEmpty(s_oper)) { 209 sPop(s_oper, &item); 210 sPush(postfix_expression, item); 211 } 212 return; 213 } 214 int cal(MyStack* postfix_expression, MyStack* s_num)//进行计算 215 { 216 int i; 217 Node n1, n2; 218 Node item; 219 //顺序取出栈中的每个元素 220 for (i = 0; i < postfix_expression->cnt; i++) { 221 //item为后缀表达式中顺序取的第i个元素 222 item = postfix_expression->sta[i]; 223 //若一直是数字 则一直放进数字栈 224 if (item.type == NUM) { 225 sPush(s_num, item); 226 continue;//开始下一次循环 227 } 228 //执行到这里证明不是数字 是运算符了 229 sPop(s_num, &n2);//从栈中拿出两个元素到n2 n1中 230 sPop(s_num, &n1); 231 if (item.val == '+') { 232 n1.val += n2.val; 233 } 234 else if (item.val == '-') { 235 n1.val -= n2.val; 236 } 237 else if (item.val == '*') { 238 n1.val *= n2.val; 239 } 240 else { 241 n1.val /= n2.val; 242 } 243 sPush(s_num, n1);//再将此次运算结果入数字栈 244 } 245 return s_num->sta[0].val;//最后数字栈中的第一个元素就是 计算结果 246 } 247 int calculate(char* s) {//进行计算 248 int ret; 249 int len; 250 if (s == NULL||(len=strlen(s))==0) { 251 return 0; 252 } 253 MyStack s_num;//数字栈 254 MyStack s_oper;//运算符栈 255 MyStack postfix_expression;//后缀表达式栈 256 if (sInit(&s_num, "数字", len)==-1|| 257 sInit(&s_oper, "运算符", len)==-1|| 258 sInit(&postfix_expression, "后缀表达式", len)==-1 259 ) //若初始化三个栈失败的话 则释放内存 return 0 260 { 261 sFree(&s_num); 262 sFree(&postfix_expression); 263 sFree(&s_oper); 264 return 0; 265 } 266 //计算后缀表达式 267 calculate_postfix_expression(&postfix_expression, &s_oper, s, len); 268 //显示后缀表达式 269 trace(&postfix_expression); 270 //使用后缀表达是进行计算 271 ret = cal(&postfix_expression, &s_num); 272 //释放栈的空间 273 sFree(&postfix_expression); 274 sFree(&s_oper); 275 sFree(&s_num); 276 //返回结果 277 return ret; 278 } 279 int main() 280 { 281 char str[10000]; 282 scanf("%[^ ]", str);//可以输入空格 回车停止输入 283 printf("计算结果为%d ", calculate(str)); 284 } 285 //例子 (((50+20)+(2*3))/14)