表达式树

「爱情、让人受尽委屈。」 2022-09-19 14:23 127阅读 0赞

在编译器内部，计算表达式的值一般是通过表达式树来解决，今天我就给大家介绍一种表达式树的实现。  
  
  
首先得到一个字符串，里边是一个表达式，算法是：  
首先得到表达式的最低优先级的运算符，然后分成左边和右边，然后求值。  
  
  
\#include<iostream>  
\#include<algorithm>  
\#include<cstdio>  
\#include<cstdlib>  
\#include<cstring>  
\#include<vector>  
using namespace std;  
//最大节点数  
const int maxn = 1000;  
//左右孩子数组，rchild\[i\]代表i的做孩子的下标  
int lchild\[maxn\],rchild\[maxn\];  
//操作符和操作数  
char op\[maxn\];  
//节点数目  
int nc = 0;  
//表达式  
char s\[100\];  
  
  
递归算法：  
首先寻找字符串表达式里边优先级最低的运算符，然后分为左边和右边继续递归，  
当只剩下一个长度的字符串时候结束递归  
int build(char \*s,int x,int y)  
\{  
    int i,c1,c2,p;  
//c1指向+-运算符  
//c2指向/和\*运算符  
    c1 = c2 = -1;  
    p = 0;  
    int u;  
    if(y-x==1)  
    \{  
        u = ++nc;  
        lchild\[u\] = rchild\[u\] = 0;  
        op\[u\] = s\[x\];  
        return u;  
    \}  
//如果是括号内部的就忽略  
    for(i=x;i<y;i++)  
    \{  
        switch(s\[i\])  
        \{  
        case '(':  
            p++;  
            break;  
        case ')':  
            p--;  
            break;  
        case '+':case '-':  
            if(!p)  
                c1 = i;  
            break;  
        case '\*':case '/':  
            if(!p)  
                c2 = i;  
            break;  
        \}  
    \}  
//如果最低优先级的不是+-运算符，指向乘除  
    if(c1<0)  
        c1 = c2;  
//说明整个表达式是在（）里边  
    if(c1<0)  
        return build(s,x+1,y-1);  
    u = ++nc;  
    lchild\[u\] = build(s,x,c1);  
    rchild\[u\] = build(s,c1+1,y);  
    op\[u\] = s\[c1\];  
    return u;  
\}  
  
  
//计算表达式树的值  
//后序遍历  
int count(int root)  
\{  
    int l,r;  
    if(rchild\[root\]!=0||lchild\[root\]!=0)  
    \{  
        l = count(lchild\[root\]);  
        r = count(rchild\[root\]);  
        switch(op\[root\])  
        \{  
        case '+':  
            return l+r;  
        case '-':  
            return l-r;  
        case '\*':  
            return l\*r;  
        case '/':  
            return l/r;  
        \}  
    \}  
    else  
    \{  
        return op\[root\]-'0';  
    \}  
\}  
  
  
int main()  
\{  
    int x,y;  
    int len;  
    strcpy(s,"(2\*3+1)");  
    len = strlen(s);  
    int root = build(s,0,len);  
    for(int i=1;i<=5;i++)  
    \{  
        cout<<i<<"-l-"<<lchild\[i\]<<"-r-"<<rchild\[i\]<<"ope"<<op\[i\]<<endl;  
    \}  
    cout<<count(1);  
    return 0;  
\}