这是《数据结构》这门课的课后练习题，很典型的一道题，总结记录一下
题目：表达式转换
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
比如a+b*c+(d*e+f)*g
string类型读入
如果遇到字母直接入队列
乘法除法优先级比加减法要高
优先级高的入站
优先级相等或者低的，先把高的入队列，再把当前的入栈
如果遇到‘（’直接入栈
如果遇到‘）’ 在堆栈中往头找，直到找到‘（’为止，并且删除堆栈中的‘（’
1. #include<iostream> 2. #include<string> 3. #include<queue> 4. #include<stack> 5. using namespace std; 6. 7. int main(){ 8. 9. stack<string> s1; 10. queue<string> q1; 11. while (!s1.empty()) 12. s1.pop();//初始化堆栈 13. while (!q1.empty()) 14. q1.pop();//初始化队列 15. 16. string s; 17. getline(cin, s);//输入 18. int len = s.size(), num = 0, i, j; 19. 20. for (i = 0; i < len; i++){ 21. string ts = ""; 22. char c = s[i], prc = s[i - 1];//c代表当前字符 prc代表前面一个字符 23. if ((c == '+' || c == '-') && (!i || prc == '(') || (c >= '0' && c <= '9')) 24. {//如果当前字符是数字或者第一个字符或者前面是左括号 直接入队列 25. if (c != '+') ts += c; 26. while (s[i + 1] == '.' || s[i + 1] >= '0' && s[i + 1] <= '9')//数字不一定是个位数 27. ts += s[++i];//数字整体写入到ts的string中 28. q1.push(ts);//进入队列 29. } 30. else if (c == '+' || c == '-') 31. { 32. int flag = 1;//flag符号控制输入 避免如(-4)这样的情况出错 33. while (flag) 34. { 35. if (s1.empty() || s1.top() == "(")//如遇到(-4)这样的情况退出 36. s1.push(ts + c), flag = 0;//如果顶部的优先级比当前的小，进入 37. else 38. { 39. q1.push(s1.top());//在压入加减之前，如果顶部是乘除，需要先拿掉 40. s1.pop(); 41. } 42. } 43. } 44. else if (c == '*' || c == '/') 45. { 46. int flag = 1; 47. while (flag) 48. { 49. if (s1.empty() || s1.top() == "(" || s1.top() == "+" || s1.top() == "-") 50. s1.push(ts + c), flag = 0;//如果顶部优先级比当前的小，就压入 51. else 52. { 53. q1.push(s1.top());//否则先把优先级高的压入队列 54. s1.pop(); 55. } 56. } 57. } 58. else if (c == '(')//左括号直接进入堆栈 59. s1.push(ts + c); 60. else if (c == ')')//右括号直接循环到遇到左括号为止 61. { 62. int flag = 1; 63. while (flag) 64. { 65. string tp = s1.top(); 66. if (tp == "(") s1.pop(), flag = 0;//遇到左括号直接退出 67. else 68. { 69. q1.push(s1.top());//没找到继续进入队列 70. s1.pop(); 71. } 72. } 73. } 74. } 75. while (!s1.empty()) 76. { 77. q1.push(s1.top());//剩余的全部依次压入堆栈 78. s1.pop(); 79. } 80. if (!q1.empty()) 81. { //c_str()作用是将string转化为C语言的字符串 82. printf("%s", q1.front().c_str()); q1.pop(); 83. }//否则string类型无法用%s这样输出 84. while (!q1.empty()) 85. { 86. printf(" %s", q1.front().c_str()); q1.pop(); 87. } 88. puts(""); 89. return 0; 90. }
