7-20 表达式转换（25 分）

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。（编者注：最后一个应该是'/'，原题就写错了）

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

输出样例:

注意：上一篇文章中我们测试得出结论，其实每个样例都是多位整数。

后序遍历二叉树并将结果存到一个字符串中。

重点：上边这些分析是个正常人都知道，问题的关键不在于此，而在于一些细节，这些细节有没有考虑才是决定能不能PASS的关键。

(1).何时创建节点申请内存，最后如何释放内存？

答：在定位出最低优先级运算符后，创建节点并赋值该运算符。

(2).如何定位最低优先级的运算符？

答：对于给定表达式，初始最低优先级为一个非常大的正数，基础优先级是0，遇到左括号基础优先级增加一个正数a(大于最高优先级)；遇到右括号基础优先级减少一个正数a；遇到运算符比较基础优先级+运算符优先级是否小于等于当前记录的最低优先级，如果是则更新最低优先级算符位置和最低优先级大小。随后，创建子树。最后，如果最低优先级没被更新过，则说明没有运算符，只需要该子树的左右子树赋值为空，将给定表达式去除左右括号后赋值为节点字符串，否则，将最低优先级运算符赋值该节点字符串，递归创建左右子树。

(3).本题隐藏的测试点，正号需要去除，怎么去除？

读取建立二叉树时：

正负号的唯一标志是该符号是第一个字符或者该符号前一个字符是‘（’。在定位最低优先级运算符时，如果遇到正负号，直接跳过。

后序遍历时：

遇到叶子带正号的直接去除正号。

(4)如何去除最后一个空格？

最后用str.erase(len-1,1)函数去除最后一个空格就好了，这里不可以直接赋值为'\0'，因为我使用的是string类型。