表达式树问题

二叉树算法表达式

问题描述:

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

基本要求:

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

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

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

基本思路:

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

读取节点时根据字符类型给与不同优先级，无括号情况下，数字优先级为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

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 22, 2019 at 08:44 pm