#include using namespace std; //后缀表达式,又称为逆波兰表达式 #pragma region C++实现的中缀表达式转后缀表达式 const int MAXSIZE = 256; /* 将中缀表达式转换为后缀表达式 参数:infix 指向中缀表达式,以回车键即\n结尾。 postfix 指向后缀表达式临时缓冲区,用来存放转换后的结果。 附转换规则:从左到右遍历中缀表达式的每个数字和符号,若是数字则直接保存在postfix数组中;若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级不大于栈顶符号,则栈顶元素依次出栈并输出,直到遇到左括号或者栈空时,才将刚才的那个符号入栈。 */ int InfixToPostfix(char *infix, char *postfix) { stack s; char c, e; int j = 0, i = 0; c = *(infix + i); //取出中缀表达式中的第一个字符 i++; while ('\n' != c) //遇到换行符,表示转换结束 { while (c >= '0' && c <= '9') //先判断一下取出的字符是否是数字,如果是数字的话,则直接存入postfix数组 { postfix[j++] = c; c = *(infix + i); i++; if (c < '0' || c > '9') //如果不是数字,则在后面添加空格,以便区分各个符号 { postfix[j++] = ' '; } } if (')' == c) //不是数字,则判断是否为右括号。[括号的优先级最高,所以,如果是右括号的话,就得先进行括号里的各种运算] { e = s.top(); s.pop(); while ('(' != e) //直到遇到左括号为止 { postfix[j++] = e; postfix[j++] = ' '; e = s.top(); s.pop(); } } else if ('+' == c || '-' == c) //如果是加减号,因为他俩的优先级最低了,所以此时先将栈里的所有符号出栈后(除非遇到左括号),再把此符号入栈 { if (!(s.size())) //如果是空栈,则直接将加减号入栈 { s.push(c); } else//如果不是空栈,首先将所有优先级大于加减的出栈,然后再把加减号入栈 { do { e = s.top(); s.pop(); if ('(' == e) { s.push(e); } else { postfix[j++] = e; postfix[j++] = ' '; } } while (s.size() && '(' != e); //将栈里的所有符号出栈(除非遇到左括号) s.push(c); //最后将新来的加减号再入栈 } } else if ('*' == c || '/' == c || '(' == c) //如果是乘除号或左括号,因为他们的优先级高,所以直接入栈。 { s.push(c); } else if ('\n' == c) //判断一下,所有符号是否都已转换完成 { break; } else //能走到这个else的,都是我不认识的符号了 { // printf("\nError:input error,the character %d cann't recognize!\n",c); return -1; } c = *(infix + i); //取出下一个字符进行转换 i++; } while (s.size()) //转换完成后,栈里可能还有没出栈的运算符号 { e = s.top(); s.pop(); postfix[j++] = e; postfix[j++] = ' '; } return true; } /* 计算后缀表达式的结果 参数:arr使用空格分隔的后缀表达式字符串。例:arr="31 5 + " result 保存计算完毕后的结果 注:如何利用栈来计算后缀表达式的结果:依次取出后缀表达式中的符号进行比较,如果是数字,则直接入栈;如果是符号,则出栈两次,弹出两个要计算的因数,进行计算,之后再将计算结果入栈。知道后缀表达式中所有符号都已比较完毕。 */ double Calculate(char *arr) { double d, e, f; //d,e 存放两个因数。f存放d,e计算后的结果. stack s; char *op; //存放后缀表达式中的每个因数或运算符 char *buf = arr; //声明bufhe saveptr两个变量,是strtok_r函数的需要。 while ((op = strtok(buf, " ")) != NULL) //利用strtok_r函数分隔字符串 { buf = NULL; switch (op[0]) { case '+': d = s.top(); s.pop(); e = s.top(); s.pop(); f = d + e; s.push(f); break; case '-': d = s.top(); s.pop(); e = s.top(); s.pop(); f = e - d; s.push(f); break; case '*': d = s.top(); s.pop(); e = s.top(); s.pop(); f = d * e; s.push(f); break; case '/': d = s.top(); s.pop(); e = s.top(); s.pop(); f = e / d; s.push(f); break; default: d = atof(op); //不是运算符,就肯定是因数了。所以,用atof函数,将字符串转换为double类型 s.push(d); break; } } double result = s.top(); s.pop(); return result; } #pragma endregion C++实现的中缀表达式转后缀表达式 // 示意图: // https://www.cnblogs.com/lulipro/p/7450886.html char in[MAXSIZE] = {0}; char postfix[MAXSIZE] = {'\0'}; int main() { //给的测试用例,后缀表达式的运算符号居然是贴在一起的,还需要手动将其分离开就行了。 string s = ""; int pos = 0; getline(cin, s); for (int i = 0; i < s.size(); ++i) { if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') { postfix[pos] = s[i]; postfix[pos + 1] = ' '; pos += 2; } else { postfix[pos] = s[i]; pos++; } } //输出后缀表达式 puts(postfix); //计算后缀表达式 cout << Calculate(postfix); return 0; }