【练习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))表达式，
出于懒，从原表达式转成后缀表达式时的括号也没扔掉【无视就好】。
#include <iostream>
#include "stack.h"
using namespace std;
using namespace stack;
template class Stack<int>;
int main(void)
{
//（1.1*1.2+1.3*1.4）+（1.5*1.6^1.7^(1.8+1.9))
calexp item[] = { ('('), (1.1), ('*'), (1.2), ('+'), (1.3), ('*'), (1.4), (')'), ('+'), ('('), (1.5), ('*'), (1.6), ('^'), (1.7), ('^'), ('('), (1.8), ('+'), (1.9), (')'), (')'), };
infix_to_postfix(item, sizeof(item)/sizeof(item[]));
for (int i = ; i < sizeof(item) / sizeof(item[]); ++i)
item[i].showcalexp();
system("pause");
}
（四）、实现代码
该说的基本都说了，其它看注释吧……………………
//练习3.20新增，中缀表达式转后缀表达式，包含错误检测
void infix_to_postfix(calexp item[], int size)
{
calexp* temp = new calexp[size];
//初检模块
//排除不以数据或正括号开头的表达式
if (item[].gettype() != CALEXP_NUMBER && item[].getopera() != '(')
{
cout << "Error: illegal beginning" << endl;
return;
}
//排除不以数据或反括号结尾的表达式
if (item[size - ].gettype() != CALEXP_NUMBER && item[size - ].getopera() != ')')
{
cout << "Error: illegal ending" << endl;
return;
}
for (int i = ; i != size - ; ++i)
{
//排除非法操作符
if (item[i].gettype() == CALEXP_OPERATOR && item[i].getlevel() == )
{
cout << "Error: illegal operator" << endl;
return;
}
//排除连续的数据
//排除连续的操作符（除非至少有一个是正括号或反括号）
if (item[i].gettype() == item[i + ].gettype())
{
if (item[i].gettype() == CALEXP_NUMBER)
{
cout << "Error: consecutive number" << endl;
return;
}
else
{
if ((item[i].getlevel() != && item[i].getlevel() != -) && (item[i + ].getlevel() != && item[i + ].getlevel() != -))
{
cout << "Error: consecutive operators" << endl;
return;
}
}
}
}
//正式转换
Stack<calexp> operators;
operators.push(calexp('!'));
int j = ;
for (int i = ; i != size; ++i)
{
//元素为数值时，直接加入临时数组
if (item[i].gettype() == CALEXP_NUMBER)
temp[j++] = item[i];
//元素为操作符时，进行相应的操作
else
{
//如果即将加入的操作符等级比栈顶操作符等级更高
//则无条件压入栈
if (item[i].getlevel() > operators.getfirst().getlevel())
operators.push(item[i]);
//如果即将加入的操作符等级比栈顶操作符等级更低或一致
else
{
//如果即将加入反括号
if (item[i].getlevel() == -)
{
temp[j++] = item[i];
//无条件弹出操作符直到最近一个正括号被弹出
while (operators.getfirst().getlevel() != && operators.getfirst().getlevel() != )
temp[j++] = operators.getpop();
if (operators.getfirst().getlevel() == )
temp[j++] = operators.getpop();
//如果在栈中未发现正括号则报错
else
{
cout << "Error: ( not found before )" << endl;
return;
}
}
//如果即将加入左结合的操作符（+,-,*,/)
else if (item[i].getlevel() == || item[i].getlevel() == )
{
//那么弹出操作符直到空栈或发现正括号为止
while (operators.getfirst().getlevel() != && operators.getfirst().getlevel() != )
temp[j++] = operators.getpop();
//把当前操作符压入
operators.push(item[i]);
}
//假如是左括号是右结合取幂操作符，无条件压入且暂时不取出
else
operators.push(item[i]);
}
}
}
//原表达式遍历完毕后，弹出操作符栈剩余符号
while (operators.getfirst().getlevel() != )
{
//如果符号中残留正括号则报错
if (operators.getfirst().getlevel() == )
{
cout << "Error: a ( without )" << endl;
return;
}
else
temp[j++] = operators.getpop();
}
//将临时数组复制回原数组
for (int i = ; i != size; ++i)
item[i] = temp[i];
delete[] temp;
}