Specific conversion method after transfer:
1. traverse the string to be calculated from left to right
2. if it is an operand, directly push it into the suffix expression stack
3. if the left bracket is used, it is directly pushed into the operator stack (the bracket is the highest priority and no comparison is required) (the priority is reduced to the lowest after being pushed into the stack to ensure that other symbols are normally pushed into the stack)
4. if it is a right parenthesis, (it means that the parenthesis is has ended), the operator at the top of the operator stack is constantly popped up and output to the suffix expression stack
Until an open parenthesis is encountered (pop-up without output)
5. operator. Compare this operator with the operator at the top of the operator stack,
If the priority is higher than the operator at the top of the stack, the operator stack will be pushed (this part of the operation cannot be performed),
If the priority is lower than or equal to the stack top operator, pop the stack top operator to the suffix expression stack and compare the new stack top operator
(lower than pop-up means that the previous part can be operated. The first output to the suffix expression stack must be a high priority operator,
Equal to pop-up because of the same priority, from left to right)
Until the priority is greater than the top of the stack operator or the stack is empty, then put the operator on the operator stack
6. if the string processing is completed, all operators will pop up from the operator stack to the suffix expression stack in sequence
How to evaluate using a suffix expression:
1. Take each value of the suffix expression in order
2. If it is a number, put it on the stack
3. If it is an operator, take two numbers from the stack for operation, and then put the result on the stack
4. Loop through the above process until the suffix expression ends. The element at the top of the stack (there is only one element in the stack) is the result
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 {//Nodes in stack 8 int val; 9 int type; 10 } Node; 11 typedef struct {//Stack 12 const char* name;//Stack name 13 Node* sta;//node 14 int size;//Maximum number of elements stored 15 int cnt;//How many elements are currently stored 16 } MyStack; 17 void trace(MyStack* s)//Traversal of stack 18 { 19 int i; 20 printf("%s The elements in the stack are:", s->name); 21 for (i = 0; i < s->cnt; i++) { 22 if (s->sta[i].type == NUM) {//If it is a number 23 printf("%d ", s->sta[i].val); 24 } 25 else {//If character 26 printf("%c ", (char)s->sta[i].val); 27 } 28 } 29 printf("\n"); 30 } 31 void sFree(MyStack* s)//Release stack 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)//Initialization stack 40 { 41 s->name = name; 42 s->size = size; 43 s->sta = (Node*)calloc(s->size, sizeof(Node));//calloc 0 is saved after application 44 if (s->sta == NULL) { 45 return -1;//allocation failed 46 } 47 s->cnt = 0;//There are 0 elements in the current stack 48 return 0;//Allocation succeeded 49 } 50 void sPush(MyStack* s, Node item)//Stack an element 51 { 52 if (s->cnt == s->size) { 53 printf("Insufficient stack space\n"); 54 return; 55 } 56 s->sta[s->cnt] = item; 57 s->cnt++; 58 return; 59 } 60 bool sIsEmpty(MyStack* s)//Determine whether the stack is empty 61 { 62 return s->cnt == 0; 63 } 64 void sPop(MyStack* s, Node* item)//Delete the top of stack element and return the value to 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)//Get stack top element to item Do not delete stack top Yuan Shu 74 { 75 if (sIsEmpty(s)) { 76 return; 77 } 78 *item = s->sta[s->cnt - 1]; 79 return; 80 } 81 bool myIsNum(char ch)//Judge whether it is a number 82 { 83 return ch >= '0' && ch <= '9'; 84 } 85 bool myIsOper(char ch)//Judge whether it is an operator 86 { 87 return ch == '+' || ch == '-' || ch == '*' || ch == '/'||ch=='('||ch==')'; 88 } 89 //Processing value 90 void procNum(MyStack* postfix_expression, char* s, int len, int* pi) 91 { 92 int i = *pi;//order i Equals the coordinates of the element currently being processed 93 int num=0;//What is the value of the current number 94 Node item_num; 95 while (myIsNum(s[i])) 96 { 97 num = num * 10 + s[i]-'0'; 98 i++; 99 } 100 //New node 101 item_num.type = NUM; 102 item_num.val = num; 103 //Number directly into the stack of suffix expression 104 sPush(postfix_expression, item_num); 105 *pi = i-1;//change calculate_postfix_expression in i Value of 106 return; 107 } 108 //Processing operator 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] == '(')//If yes( Directly stored in the operator stack 116 { 117 item.type = OPERATION; 118 item.val = s[i]; 119 sPush(s_oper, item); 120 } 121 else if (s[i] == ')')//If) Pop up to(Until 122 { 123 int flag = 0;//Is it found ( 124 while (!sIsEmpty(s_oper)) { 125 sPop(s_oper, &pop_item); 126 if (pop_item.val == '(') {//Exit if left parenthesis is found 127 flag = 1; 128 break; 129 } 130 sPush(postfix_expression, pop_item);//If the left parenthesis is not found, it is always removed from the operator stack pop 131 } 132 if (!flag) 133 { 134 printf("Brackets do not match!"); 135 exit(0); 136 } 137 } 138 //If it's multiplication and division 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 //If the top of the current operator stack is+ - ( 146 //be* /High level jumps out of the loop 147 if (top_item.val == '+' || top_item.val == '-' || top_item.val == '(') { 148 break; 149 } 150 //If the current operator stack top is not+ - ( then is* / 151 //You need to* / pop finish 152 sPop(s_oper, &pop_item); 153 sPush(postfix_expression, pop_item); 154 } 155 //To be* /Push 156 sPush(s_oper, item); 157 } 158 //If yes + - 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 //If the top of the current operator stack is ( 166 //If the current operator level is higher, the loop will jump out 167 if (top_item.val == '(') { 168 break; 169 } 170 //If the current operator stack top is not ( then is+ - * / 171 //You need to+ - * /pop finish 172 sPop(s_oper, &pop_item); 173 sPush(postfix_expression, pop_item); 174 } 175 //To be+ - Push 176 sPush(s_oper, item); 177 } 178 else 179 { 180 printf("An element that is not a space, a number, or an operator was entered %c\n", s[i]); 181 exit(0); 182 } 183 return; 184 } 185 //The calculated suffix expression is stored in s_trans in 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] == ' ') {//Skip when current input is a space 194 continue; 195 } 196 if (myIsNum(s[i])) {//When the current is a number 197 procNum(postfix_expression, s, len, &i); 198 continue; 199 } 200 if (myIsOper(s[i])) {//The handler that enters the operation when the current is an operator 201 procOper(postfix_expression, s_oper, s, len, &i); 202 continue; 203 } 204 printf("An element that is not a space, a number, or an operator was entered %c\n", s[i]); 205 exit(0); 206 } 207 //If the operation stack is not empty pop Rerun the elements in the shipment stack push To suffix expression stack 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)//Calculate 215 { 216 int i; 217 Node n1, n2; 218 Node item; 219 //Sequentially fetch each element in the stack 220 for (i = 0; i < postfix_expression->cnt; i++) { 221 //item Is the ordinal number in the suffix expression i Elements 222 item = postfix_expression->sta[i]; 223 //If it is always a number, it is always put into the number stack 224 if (item.type == NUM) { 225 sPush(s_num, item); 226 continue;//Start next cycle 227 } 228 //So far, it is proved that it is not a number but an operator 229 sPop(s_num, &n2);//Take two elements from the stack to n2 n1 in 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);//Then put the operation result into the number stack 244 } 245 return s_num->sta[0].val;//Finally, the first element in the number stack is the calculation result 246 } 247 int calculate(char* s) {//Calculate 248 int ret; 249 int len; 250 if (s == NULL||(len=strlen(s))==0) { 251 return 0; 252 } 253 MyStack s_num;//Digital stack 254 MyStack s_oper;//Operator stack 255 MyStack postfix_expression;//Suffix expression stack 256 if (sInit(&s_num, "number", len)==-1|| 257 sInit(&s_oper, "operator", len)==-1|| 258 sInit(&postfix_expression, "Postfix Expression ", len)==-1 259 ) //If the initialization of three stacks fails, the memory will be released return 0 260 { 261 sFree(&s_num); 262 sFree(&postfix_expression); 263 sFree(&s_oper); 264 return 0; 265 } 266 //Evaluate suffix expression 267 calculate_postfix_expression(&postfix_expression, &s_oper, s, len); 268 //Show suffix expression 269 trace(&postfix_expression); 270 //Use suffix to express yes for calculation 271 ret = cal(&postfix_expression, &s_num); 272 //Free up stack space 273 sFree(&postfix_expression); 274 sFree(&s_oper); 275 sFree(&s_num); 276 //Return results 277 return ret; 278 } 279 int main() 280 { 281 char str[10000]; 282 scanf("%[^\n]", str);//You can enter a space enter to stop entering 283 printf("The calculation result is%d\n", calculate(str)); 284 } 285 //example (((50+20)+(2*3))/14)