【练习3.20】
a.编写一个程序将中缀表达式转换为后缀表达式，该中缀表达式含括号及四则运算。
b.把幂操作符添加到你的指令系统中去。
c.编写一个程序将后缀表达式转化为中缀表达式。
Answer:
花了好大力气把a，b就放一起写好了，终于知道为啥说编译原理难了，就这么简单的句法分析也好坑爹。
c真的不打算写了，如果以后要学编译原理的话再继续吧。
（一）、首先是核心思路，还是比较清晰的。
①、对于左结合运算符的出入栈，规则很简单：
如果栈顶运算符为左结合的，那么有同级别或低级别优先级运算符即将入栈时，则运算符持续弹出，直至遇左括号或栈清空为止。
解释一下为何优先级相等时也要立即弹出，其实，对于具有结合律的操作，遇到更低级别的运算符才跳出也完全没问题。
比如2*3*4后缀表达式可以写成2 3 4 * * ，也可以写成2 3 * 4 * ，无非就是2*(3*4)还是2*3*4的运算区别罢了。
但是如果对于减法这种2-3-4，写成2 3 - 4 -才是正确的，2 3 4 - -实际上表达的是2-(3-4)=2-3+4完全和原式子不一样。
故而，栈顶左结合运算符即使在遇到同等优先级别的运算符时，也必须跳出。
②、至于右结合运算符的出入栈，唯一也是最大的区别在于：
仅对于低级别优先级即将入栈时，才持续弹出运算符；而同级别运算符即将入栈时维持不变。
用例子2^3^4来解释的话，数学上其定义实际上是2^3^4 = 2^(3^4)。
从而如果2^3^4采用同级别即跳出原则，会写成2 3 ^ 4 ^即(2^3)^4，和定义不一致。
③、对于组合运算符，正括号无条件入栈，反括号无条件出栈至找到正括号为止
（二）、该死的错误检测
因为计算后缀表达式没写错误检测，于是这个就写写吧。
写起来才知道坑，简直是让人不想写c小题的最重要原因【毕竟只是在学数据结构又不是在学编译原理啊喂(╯‵□′)╯︵┻━┻】。
想了一下，原表达式可能出现的错误有：
①、操作符非法
②、头元素既不是数字，也不是正括号
③、尾元素既不是数字，也不是反括号
④、连续出现数字
⑤、连续出现操作符，当两个操作符中没有一个是正括号或者反括号时
⑥、反括号导致出栈时找不到对应的正括号
⑦、非反括号导致出栈时意外地发现正括号
……………………
总之这些都考虑了，也都写了相应的错误，但是搞着搞着还是发现漏了情况，
比如表达式“2+(3+4)5”一看就知道是不合规的，但是它偏偏就不在前面七种情况里，你特么在逗我(╯‵□′)╯︵┻━┻！
所以，算了懒得写了……核心功能能实现就行。
（三）、测试代码
最后测了这么一段(1.1*1.2+1.3*1.4)+(1.5*1.6^1.7^(1.8+1.9))表达式，
出于懒，从原表达式转成后缀表达式时的括号也没扔掉【无视就好】。
1 #include <iostream> 2 #include "stack.h" 3 using namespace std; 4 using namespace stack; 5 template class Stack<int>; 6 int main(void) 7 { 8 //（1.1*1.2+1.3*1.4）+（1.5*1.6^1.7^(1.8+1.9)) 9 calexp item[] = { ('('), (1.1), ('*'), (1.2), ('+'), (1.3), ('*'), (1.4), (')'), ('+'), ('('), (1.5), ('*'), (1.6), ('^'), (1.7), ('^'), ('('), (1.8), ('+'), (1.9), (')'), (')'), }; 10 infix_to_postfix(item, sizeof(item)/sizeof(item[0])); 11 for (int i = 0; i < sizeof(item) / sizeof(item[0]); ++i) 12 item[i].showcalexp(); 13 system("pause"); 14 }
（四）、实现代码
该说的基本都说了，其它看注释吧……………………
1 //练习3.20新增，中缀表达式转后缀表达式，包含错误检测 2 void infix_to_postfix(calexp item[], int size) 3 { 4 calexp* temp = new calexp[size]; 5 //初检模块 6 //排除不以数据或正括号开头的表达式 7 if (item[0].gettype() != CALEXP_NUMBER && item[0].getopera() != '(') 8 { 9 cout << "Error: illegal beginning" << endl; 10 return; 11 } 12 //排除不以数据或反括号结尾的表达式 13 if (item[size - 1].gettype() != CALEXP_NUMBER && item[size - 1].getopera() != ')') 14 { 15 cout << "Error: illegal ending" << endl; 16 return; 17 } 18 for (int i = 0; i != size - 1; ++i) 19 { 20 //排除非法操作符 21 if (item[i].gettype() == CALEXP_OPERATOR && item[i].getlevel() == 0) 22 { 23 cout << "Error: illegal operator" << endl; 24 return; 25 } 26 //排除连续的数据 27 //排除连续的操作符（除非至少有一个是正括号或反括号） 28 if (item[i].gettype() == item[i + 1].gettype()) 29 { 30 if (item[i].gettype() == CALEXP_NUMBER) 31 { 32 cout << "Error: consecutive number" << endl; 33 return; 34 } 35 else 36 { 37 if ((item[i].getlevel() != 4 && item[i].getlevel() != -1) && (item[i + 1].getlevel() != 4 && item[i + 1].getlevel() != -1)) 38 { 39 cout << "Error: consecutive operators" << endl; 40 return; 41 } 42 } 43 } 44 } 45 //正式转换 46 Stack<calexp> operators; 47 operators.push(calexp('!')); 48 int j = 0; 49 for (int i = 0; i != size; ++i) 50 { 51 //元素为数值时，直接加入临时数组 52 if (item[i].gettype() == CALEXP_NUMBER) 53 temp[j++] = item[i]; 54 //元素为操作符时，进行相应的操作 55 else 56 { 57 //如果即将加入的操作符等级比栈顶操作符等级更高 58 //则无条件压入栈 59 if (item[i].getlevel() > operators.getfirst().getlevel()) 60 operators.push(item[i]); 61 //如果即将加入的操作符等级比栈顶操作符等级更低或一致 62 else 63 { 64 //如果即将加入反括号 65 if (item[i].getlevel() == -1) 66 { 67 temp[j++] = item[i]; 68 //无条件弹出操作符直到最近一个正括号被弹出 69 while (operators.getfirst().getlevel() != 0 && operators.getfirst().getlevel() != 4) 70 temp[j++] = operators.getpop(); 71 if (operators.getfirst().getlevel() == 4) 72 temp[j++] = operators.getpop(); 73 //如果在栈中未发现正括号则报错 74 else 75 { 76 cout << "Error: ( not found before )" << endl; 77 return; 78 } 79 } 80 //如果即将加入左结合的操作符（+,-,*,/) 81 else if (item[i].getlevel() == 1 || item[i].getlevel() == 2) 82 { 83 //那么弹出操作符直到空栈或发现正括号为止 84 while (operators.getfirst().getlevel() != 0 && operators.getfirst().getlevel() != 4) 85 temp[j++] = operators.getpop(); 86 //把当前操作符压入 87 operators.push(item[i]); 88 } 89 //假如是左括号是右结合取幂操作符，无条件压入且暂时不取出 90 else 91 operators.push(item[i]); 92 } 93 } 94 } 95 //原表达式遍历完毕后，弹出操作符栈剩余符号 96 while (operators.getfirst().getlevel() != 0) 97 { 98 //如果符号中残留正括号则报错 99 if (operators.getfirst().getlevel() == 4) 100 { 101 cout << "Error: a ( without )" << endl; 102 return; 103 } 104 else 105 temp[j++] = operators.getpop(); 106 } 107 //将临时数组复制回原数组 108 for (int i = 0; i != size; ++i) 109 item[i] = temp[i]; 110 delete[] temp; 111 }