算术表达式的转换——算术表达树

ゝ一纸荒年。 2022-06-14 11:41 238阅读 0赞

Think:  
1知识感悟：算术表达式的转换可以思考通过后缀表达式建树，然后分别进行前序遍历，中序遍历，后序遍历即可得到前缀表达式，中缀表达式，后缀表达式

[SDUT题目链接][SDUT]  
[建议参考博客][Link 1]

算术表达式的转换  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。  
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。

Input  
输入一算术表达式，以\\’\#\\’字符作为结束标志。（数据保证无空格,只有一组输入）

Output  
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。

Example Input  
a\*b+(c-d/e)\*f\#

Example Output  
\+*ab*\-c/def  
a\*b+c-d/e\*f  
ab\*cde/-f\*+

Hint

Author

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    struct node {
        char s;
        struct node *l;
        struct node *r;
    };
    
    char sa[104], sb[104], sc[104];
    
    int p;
    
    void First(struct node *q);/*前序遍历*/
    void Infix(struct node *q);/*中序遍历*/
    void Postfix(struct node *q);/*后序遍历*/
    void H();
    
    int main(){
        int d = 0, i;
        scanf("%s", sa);
        H();
        struct node *po[104] = {NULL}, *pi;
        for(i = 0; i < p; i++){
            if(sb[i] >= 'a' && sb[i] <= 'z'){
                pi = (struct node *)malloc(sizeof(struct node));
                pi->s = sb[i];
                pi->l = NULL;
                pi->r = NULL;
                po[d++] = pi;
            }
            else {
                pi = (struct node *)malloc(sizeof(struct node));
                pi->s = sb[i];
                pi->r = po[d-1];
                d--;
                pi->l = po[d-1];
                d--;
                po[d++] = pi;
            }
        }
        First(po[0]);
        printf("\n");
        Infix(po[0]);
        printf("\n");
        Postfix(po[0]);
        printf("\n");
        return 0;
    }
    void H(){
        int x = 0, y = 0;
        for(p = 0; sa[p] != '#'; p++){
            if(sa[p] >= 'a' && sa[p] <= 'z')
                sb[x++] = sa[p];
            else if(sa[p] == '+' || sa[p] == '-'){
                while(y != 0 && sc[y-1] != '('){
                    sb[x] = sc[y-1];
                    x++;
                    y--;
                }
                sc[y++] = sa[p];
            }
            else if(sa[p] == '*' || sa[p] == '/'){
                while(y != 0 && (sc[y-1] == '*' || sc[y-1] == '/')){
                    sb[x] = sc[y-1];
                    x++;
                    y--;
                }
                sc[y++] = sa[p];
            }
            else if(sa[p] == '(')
                sc[y++] = sa[p];
            else if(sa[p] == ')'){
                while(sc[y-1] != '('){
                    sb[x] = sc[y-1];
                    x++;
                    y--;
                }
                y--;
            }
        }
        while(y != 0){
            sb[x] = sc[y-1];
            x++;
            y--;
        }
        sb[x] = '\0';
    }
    void First(struct node *q){
        if(q != NULL){
            printf("%c", q->s);
            First(q->l);
            First(q->r);
        }
    }
    void Infix(struct node *q){
        if(q != NULL){
            Infix(q->l);
            printf("%c", q->s);
            Infix(q->r);
        }
    }
    void Postfix(struct node *q){
        if(q != NULL){
            Postfix(q->l);
            Postfix(q->r);
            printf("%c", q->s);
        }
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-06-19 17:36:39
    ****************************************************/

[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2484.html
[Link 1]: http://blog.csdn.net/lin375691011/article/details/9372245