中缀/后缀表达式转换-使用四则混合运算表达式生成树

很多资料讨论了四则混合运算的中缀表达式和后缀表达式的变换方法，有的很简单，有的很复杂，然而这种简单和复杂只是表现在程序上的，肉眼观察加人工操作完成这样的任何实际上十分简单，因为人脑习惯于于用自己的方式来解决问题，如果要写程序，那么就要迎合电脑的习惯，这种习惯的转换和移风易俗一样困难。

括号的引入加大了复杂度，然而括号的加入实际上使问题更简单了，人们习惯于去掉括号，然而简单的办法却是加上括号，当你加满括号的时候，中缀转后缀就简单多了，比如下面的式子：

3+5*7+2

加上括号后即为：

((3+(5*7))+2)

从内到外，将运算符和后操作数互换即可：

((3(57*)+)2+)

然后去掉括号：

357*+2+

便是结果，这是为什么呢？实际上原因很简单，那就是四则运算(实际上还有开方，次幂运算)的操作符都是二元操作符号，你只要找出是哪两个操作数进行计算即可，使用括号可以用一种统一的方法做到这一点，最终的算法其实是一个递归的算法。本文不准备实现这个递归的算法，因为那是手工动作的一种翻译。本文实现一种通用的转换算法，那就是先把中缀式子转化为一棵树，然后使用不同的遍历遍历方式得到不同的表达式：

1.前序遍历：前缀表达式

2.中序遍历：中缀表达式

3.后序遍历：后缀表达式

看到这些词汇以及思想，很多人可能想到了编译原理中的语法树，记得《龙书》中有所讲到，还有一大堆公式以及定理，很多人几乎都能说出一大堆。想到这，我就搞不明白了，科举考试废除107年了快，怎么还有那么多人遇到问题不自己思考而总喜欢引经据典呢？遇到问题第一步，你要先用最最纯粹的方法实现了它，然后再查阅典籍，拨乱反正。动不动就先搞专业术语，比如上去就喷出O(n)，上去就哈希，上去就table的，实际上很多都是只知道个名字而已。就算最垃圾的算法，也要先自己实现，然后在查漏补缺，大学期间学了几招用到现在，实际山阻碍了你自己思考的机会。

幸亏我不懂什么专业名词，也不懂什么语法生成树，于是我纯粹的实现一棵树。实现这棵树之前，有甚多工作要做，毕竟没有任何可以借鉴的，就算有，也懒得看，就算看，也不一定能看懂。在构造生成树之前，幸运的是，我们知道四则混合运算只有两种优先级，而且同一个优先级运算都是自左向右的，这就大体确定了这棵树的结构：自下而上，自左向右。对于优先级的安排，那自然是右下优先级高于右上优先级，因此，乘法和除法位于右下处，而加法和减法位于右上处，同一优先级计算向右上延伸，不同优先级计算从低到高向右下延伸，如下图：

略

事实上，从这个图可以看出，从左到右，只有两层，第一层是加减，第二层是乘除，从下到上，按照字面的顺序排列，自左向右，递归深入，先计算右边的再返回左边的，因此对于乘除而言，只要返回1级或者2级，而对于加减而言，则要返回1级，2级，或者3级，因此统一的办法就有了。

由于只有两个优先级，事情很好办了。只要考虑到所有的优先级切换情况即可。第一步先实现一个简单的，不考虑括号，因为括号里面的内容实际上可以作为一个操作数，使用递归方法求出它即可，然后将其作为一个操作数。

如果在生成树的时候，直接考虑括号，那么事情就复杂了很多，因为括号优先级最高，而且还不是像运算符那样结合操作数的字符，因此把括号括住的成分单独作为一个操作数比较好，这样就可以递归的实现了。首先给出没有括号时的代码，为了简化字符串处理，我没有使用字符串，而是使用了字符，因此不支持两位的数字算式：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct string_node {
    char  tag;  //定义字符
    struct  string_node *left;
    struct string_node *right;
    struct string_node *parent;
};
struct string_node *gen_sub_tree(char*str, int len)
{
    struct string_node *root;
    int i = 0;
    for (i = 0; i < len; i++) {
        struct string_node *node = (struct string_node*)calloc(1, sizeof(structstring_node));
        node->tag =str[i];
        if(isdigit(str[i])) {
            if (i != 0) {//运算由左至右，除了第一个操作数，其它全部为右操作数，高优先级的会处在树的旁支
                root->right = node;
                node->parent = root;
            }
            root = node;
        } else if((str[i] == 'x') || (str[i] == '/')) {
         //处理乘除运算符
            struct  string_node *temp_root = NULL, *temp_parent = NULL;
            if (root->parent &&(root->parent->tag == '+' || root->parent->tag == '-')) {
                temp_parent = root->parent;
                temp_root = root;
            } else if(root->parent) {
                temp_parent =root->parent->parent;
                temp_root = root->parent;
            } else {
                temp_root = root;
            }
            node->parent = temp_parent;
            if (temp_parent)
                temp_parent->right = node;
            node->left = temp_root;
            temp_root->parent = node;
            root = node;
       } else if (str[i] == '+' || str[i] == '-') {
       //处理加减运算符
            struct string_node *temp_root =NULL, *temp_parent = NULL;
            if (root->parent &&root->parent->parent  &&(root->parent->tag == 'x' || root->parent->tag == '/')) {
                temp_root =root->parent->parent;
            } else if (root->parent&& !root->parent->parent){
                temp_root = root->parent;
            } else {
                temp_root = root;
            }
            node->left = temp_root;
            temp_root->parent = node;
            root = node;
       }
    }
   //找到树根，返回调用者
    while (root->parent) {
        root = root->parent;
    }
    return root;
}

int main(int argc, char **argv)
{
    struct string_node *root;
    char str[40] ={'1','+','0','+','2','x','5','+','3','x','4','x','2', '-', '7'};
    root = NULL;
    root = gen_sub_tree(str, 100);
    print_result(root);
    return 0;
}
//输出结果
void print_result(struct string_node*p)
{

     if(p != NULL) {
         //此为后缀表达式，根据printf的位置不同可以得到不同的X缀表达式
         print_result(p->left);
         print_result(p->right);
         printf("%c\n", p->tag);
     }
}

那么加上括号又有何难，只需要加入对’(‘和’)’的解析即可喽，递归调用gen_sub_tree即可。以下为加入括号处理的代码：

#include <stdio.h>
#include <stdlib.h>
struct string_node {
    char  tag;
    struct string_node *left;
    struct string_node *right;
    struct string_node *parent;
};
void print_result(struct string_node*p)
{
    if (p != NULL){
        print_result(p->left);
        print_result(p->right);
        printf("%c\n", p->tag);
    }
}

struct string_node *gen_sub_tree(char*str, int len)
{
   struct string_node *root = NULL;
   static int thre = 0;
    int i = 0, j = 0;;
    int brackets = 0;
    char brackets_bulk[40] = {0};
    printf("orig:%s\n", str);
    thre ++;
    for (i = 0; i < len; i++) {
        struct string_node *node = (structstring_node*)calloc(1, sizeof(struct string_node));
        node->tag = (char *)calloc(1, 10);
        node->tag = str[i];
        if (str[i] == '(') {
            if (brackets)
                brackets_bulk[j++] = str[i];
            brackets++;
        } else if (str[i] == ')' ) {
                brackets--;
                if (brackets)
                    brackets_bulk[j++] =str[i];
                else {
                    struct string_node*node_brackets = gen_sub_tree(brackets_bulk, 40);
                    if (root) {
                        root->right =node_brackets;
                       node_brackets->parent = root;
                    }
                    root = node_brackets;
                    brackets = 0;
                }
        } else if (brackets) {
            brackets_bulk[j++] = str[i];
        } else if (!brackets &&isdigit(str[i])) {
            if (i != 0) {//
                root->right = node;
                node->parent = root;
            }
            root = node;
        } else if (!brackets &&((str[i] == 'x') || (str[i] == '/'))) {
            struct string_node *temp_root =NULL, *temp_parent = NULL;
            if (root->parent &&(root->parent->tag == '+' || root->parent->tag == '-')) {
                temp_parent = root->parent;
                temp_root = root;
            } else if(root->parent) {
                temp_parent =root->parent->parent;
                temp_root = root->parent;
            } else {
                temp_root = root;
            }
            node->parent = temp_parent;
            if (temp_parent)
                temp_parent->right = node;
            node->left = temp_root;
            temp_root->parent = node;
            root = node;
        } else if (!brackets && (str[i]== '+' || str[i] == '-')) {
            struct string_node *temp_root =NULL;
            if (root->parent &&root->parent->parent  &&(root->parent->tag == 'x' || root->parent->tag == '/')) {
                temp_root =root->parent->parent;
            } else if (root->parent&& !root->parent->parent){
                temp_root = root->parent;
            } else {
                temp_root = root;
            }
            node->left = temp_root;
            temp_root->parent = node;
            root = node;
        }
    }
    while (root->parent) {
        root = root->parent;
    }
    return root;
}
int main(intargc, char **argv)
{
        struct string_node *root;
        char str[40] ={'3','x','(','(','1','+','(','0','+','2',')',')','x','5','+','3',')','x','4','x','2','-', '7'};
        root = NULL;
        root = gen_sub_tree(str, 100);
        print_result(root);
       return 0;
}

从这个题目可以看出，其实没有学过编译原理，没有学过语法生成树也能自己构建一棵树，问题在于，你被自己学过的知识困住了么？

所有没有学历的，自学成才的人们，以及刚毕业还没有找到工作的本科生，研究生们，与其去背诵一些只知道个名字的词汇，还不如自己动手实现一些哪怕十分丑陋的东西，知识不丰富不可怕，最怕的是缺少了学习的能力，竞争激烈的社会不要被那些道貌岸然的人们所吓倒，哥不是还屹立着吗？做一点是一点，即使被挑出N多毛病，那是好事，改掉后你将趋于完美，上述的算法代码很凌乱，也有很多的bug，然而却是一种实现。王侯将相，宁有种乎？难道技校出身的就一定比不上科班出身的血统高贵吗？虽然大多数的企业都在乎出身，哥也被玩弄了好几回，但是不要气馁，不要怕，特别是不要怕那些所谓的科班程序员们，要知道，早在战国时期，一个布衣农夫就能轻而易举捅死一个身裹绫罗绸缎的人，绸缎，布料虽好，但不防身，只是一种象征而已。