表达式树问题

in 数据结构 with 0 comment

问题描述:

表达式树是二叉树的一种应用,叶子是操作数,其余结点为操作符。请编程实现表达式树的建立和遍历。

基本要求:

表达式支持的运算符自行设定,例如,四则运算。

采用某种方式输入表达式,例如后缀表达式形式。将用户输入的表达式创建成如上图所示的表达式树。

遍历该表达式树,分别输出该表达式的中缀表达式和后缀表达式形式。

WINWORD_MD61uJpYoG.png

基本思路:

以字符串的形式读取表达式,每次读取一个节点,然后根据优先级旋转。

读取节点时根据字符类型给与不同优先级,无括号情况下,数字优先级为9,加减优先级为1,乘除优先级为2。有括号加入时,数字、加减、乘除优先级增加10括号的深度,括号优先级为10括号的深度。例如一层括号里,加减优先级为11。优先级记录在flag中,flag模10为9时,代表数字,data有效,其他情况,char有效。

每次读取完一个节点后,将原有根节点作为此节点的左子节点。再根据节点优先级进行旋转,使得其优先级不大于左子树优先级。

计算结果时,递归式运算。如果节点为运算符,则对左右子树进行该运算;如果节点为数字,则直接返回数字值;如果节点为括号,则该节点一定为右括号,且该节点的左节点一定为对应的左括号,左括号的右子树为括号里面的表达式,递归该子树得到相应结果

代码实现:

以CPP为例:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int flag;//1为符号,9为数字 
    int data;
    char c;
    Node *l,*r;//左右子树
}Node;
/**
 * @ch为字符指针,代表当前读取位置
 * @depth 记录当前括号深度
 */
Node* readNode(char * &ch,int & depth){
    if(*ch=='\0')
        return NULL;
    Node* nnode=(Node*)malloc(sizeof(Node));//读取一个节点
    nnode->l = nnode->r = NULL;
    if(*ch<='9'&&*ch>='0'){//节点为数字
        nnode->flag = 9;
        nnode->data = 0;
        while(*ch<='9'&&*ch>='0'){
            int t =*ch - '0';
            nnode->data = nnode->data * 10 + t;
            ch++;
        }ch-- ;
    }else if(*ch=='+'||*ch=='-'){//节点为+-
        nnode->flag = 1;
        nnode->c = *ch;
    }else if(*ch=='*'||*ch=='/'){//节点为*/
        nnode->flag = 2;
        nnode->c = *ch;
    }else if(*ch=='('){//节点为左括号,深度+1
        nnode->flag = 0;
        nnode->c = *ch;
        depth++;
    }else if(*ch==')'){//节点为右括号,深度-1
        nnode->flag = 10;
        nnode->c = *ch;
        depth--;
    }else{
        return NULL;
    }
    ch++;
    nnode->flag += depth*10;//加上当前深度*10
    return nnode;
}
/**
 * 根据flag优先级进行旋转,优先级越大越靠近叶节点
 */
Node* rotate(Node *& node){
    if(node==NULL||node->l==NULL||node->flag<=node->l->flag){
        return node;//空节点或单个节点或其优先级不大于左子树优先级
    }
    else{//右旋操作
        Node *  tmp = node->l;
        node->l = node->l->r;
        tmp->r = node;
        node = tmp;
        rotate(node->r);
        return node;
    }
}
/**
 * 计算表达式树的值
 */
double getResult(Node *root){
    if(root==NULL){
        printf("ERROR!");
        return -1;
    }
    else if(root->flag%10==9){//为数字节点,直接返回data值
        return root->data;
    }else if(root->flag%10==0){//为右括号节点,返回括号里表达式的值
        return getResult(root->l->r);
    }else if(root->c=='+'){
        return getResult(root->l) + getResult(root->r);
    }else if(root->c=='-'){
        return getResult(root->l) - getResult(root->r);
    }else if(root->c=='*'){
        return getResult(root->l) * getResult(root->r);
    }else if(root->c=='/'){
        double tmp = getResult(root->r);
        if((abs(tmp)<=0.000001)){ //被除数是否为0
            printf("error");
            exit(1);
        }
        else return getResult(root->l) / getResult(root->r);
    }else{
        return -1;
    }
}

void printTIn(Node* root){
    if(root!=NULL){
        printTIn(root->l);
        if(root->flag%10==9){printf("%d ", root->data);}
        else printf("%c ", root->c);
        printTIn(root->r);
    }
}

void printTPre(Node* root){
    if(root!=NULL){
        if(root->flag%10==9){printf("%d ", root->data);}
        else printf("%c ", root->c);
        printTPre(root->l);
        printTPre(root->r);
    }
}

void printTPost(Node* root){
    if(root!=NULL){
        if(root->flag%10==9){printf("%d ", root->data);}
        else printf("%c ", root->c);
        printTPost(root->l);
        printTPost(root->r);
    }
}

int main(void){
    int depth = 0;
    char a[100] = {};
    printf("Please input the string:");
    scanf("%s", a);
    char *ch = a;
    Node *tmp,*root=NULL;
    while(*ch!='\0'){
        tmp = root;
        root=readNode(ch,depth);//读取新节点
        root->l = tmp;
        rotate(root);//旋转
    }
    printf("Pre:\n");
    printTPre(root);
    printf("\nIn:\n");
    printTIn(root);
    printf("\nPost:\n");
    printTPost(root);
    printf("\nresult = %.2lf",getResult(root));
    return 0;
}

样例:

//输入 2-4*(4-5/32+(5*2)-2)*2+1
Please input the string:2-4*(4-5/32+(5*2)-2)*2+1
Pre:
+ - 2 * * 4 ) ( - + - 4 / 5 32 ) ( * 5 2 2 2 1
In:
2 - 4 * ( 4 - 5 / 32 + ( 5 * 2 ) - 2 ) * 2 + 1
Post:
+ - 2 * * 4 ) ( - + - 4 / 5 32 ) ( * 5 2 2 2 1
result = -91.75
Responses