怎么将中缀式转换成后缀式 C语言 递归

如何将中缀式转换成后缀式 C语言 递归
如输入
（5*(((9+8)*（4*6))+7))
转换成
598+46**7+*
如上所述对于中缀式 两个操作数进行运算时必须要用括号括起来！
使用堆栈 不用说了 很简单 但是递归怎么做？
[解决办法]

引用:

中缀： 
1，输出根节点；2，递归输出左子树；3，递归输出右子树。

后缀：
1，递归输出左子树；2递归输出右子树；3，输出根节点。

首先要将中缀式子构造成一颗二叉树，数字为叶子，符号为非叶节点。然后按后缀的递归方式。

写错了，应该是：
前缀： 
1，输出根节点；2，递归输出左子树；3，递归输出右子树。
中缀： 
1，递归输出左子树；2，输出根节点；3，递归输出右子树。

[解决办法]
用中缀表达式建立树，好像也很麻烦。后续递归遍历简单。
还是直接解析更容易些。

[解决办法]

#include <ctype.h>
#include <stdio.h>
#include <string.h>


int transfer(char const* _ori,char* _dst)
{
    char last_opt = ' ';
    char last_last_opt = ' ';
    char const* ori = _ori;
    char *      dst = _dst;
    char buf[1024] = {0,};
    int len = 0;

    while (0 != *ori) {
        if (isdigit(*ori)) {
            *dst++ = *ori++;
            if ('*' == last_opt 
[解决办法]
 '/' == last_opt) {
                *dst++ = last_opt;
                last_opt = last_last_opt;
                last_last_opt = ' ';
            }
        }
        else if ('+' == *ori  
 
[解决办法]
 '-' == *ori) {
            if ('+' == last_opt 
[解决办法]
 '-' == last_opt) {
                *dst++ = last_opt;
            }
            last_opt = *ori++;
        }
        else if ('*' == *ori 
[解决办法]
 '/' == *ori) {
            last_last_opt = last_opt;
            last_opt = *ori++;
        }
        else if ('(' == *ori) {
            ori++;
            len = transfer(ori,buf);
            ori += len;
            strcpy(dst,buf);
            dst += strlen(buf);
        }
        else if (')' == *ori 
[解决办法]
 0 == *ori) {
            if (' ' != last_opt)
                *dst++ = last_opt;
            ori++;
            break;
        }
    }

    *dst = 0;

    return ori - _ori;
}

int main(int argc, char *argv[])
{
    char dst[1024] = {0,};
    char const* ori = "(5*(((9+8)*(4*6))+7))";
    int len = 0; 
 

    len = transfer(ori,dst);
    printf("%s\n",dst);
//    printf("len: %d strlen: %d\n",len,strlen(ori));

    return 0;
}

查看更多 下一篇