C++实现python的eval函数用一个结构体记录数组或操作符把表达式切割为结点中缀表达式生成后缀表达式后缀表达式计算实值完整代码

89 阅读 0 评论 59 点赞

我是靠谱客的博主自由蓝天，这篇文章主要介绍C++实现python的eval函数用一个结构体记录数组或操作符把表达式切割为结点中缀表达式生成后缀表达式后缀表达式计算实值完整代码，现在分享给大家，希望可以做个参考。

用一个结构体记录数组或操作符

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct Node{//运算结点，记录数字或运算符号
    bool isop;
    char op;
    int num;
    Node(){}
    Node(int d){
        num=d;
        isop=0;
    }
    Node(char op_){
        op=op_;
        isop=1;
    }
    void output(){
        if(isop) cout<<op;
        else cout<<num;
    }
}Node;

把表达式切割为结点

类似词法分析
只能对单个数字进行切割，待优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<Node> exp2nodes(string exp){
    vector<Node> ans;
    FF(i,exp.size()){
        char c=exp[i];
        if(c>='0' && c<='9'){
            ans.push_back((int)(c-'0'));
        }else{
            ans.push_back(c);
        }
    }
    return ans;
}

中缀表达式生成后缀表达式

https://www.cnblogs.com/hantalk/p/8734511.html

复制代码

int getPriority(char op){
    switch(op){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

vector<Node> yieldPostOrderExpress(vector<Node> &in){
    vector<Node> post;
    Node ops[LEN];
    int top=-1;//栈顶指针
    FF(i,in.size()){
        Node u=in[i];
        if(u.isop){
            if(u.op=='('){
                ops[++top]=u;//入栈
            }else if(u.op==')'){
                while(top>=0){
                    Node p=ops[top--];
                    if(p.op=='('){
                        break;
                    }else{
                        post.push_back(p);
                    }
                }
            }else{
                while(top>=0 && getPriority(u.op) <= getPriority(ops[top].op)){
                    post.push_back(ops[top--]);//持续出栈直到满足优先级
                }
                ops[++top]=u;//入栈
            }

}else{
            post.push_back(u);
        }
    }
    //处理剩下的栈
    while(top>=0){
        post.push_back(ops[top--]);
    }
    return post;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int getPriority(char op){
    switch(op){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

vector<Node> yieldPostOrderExpress(vector<Node> &in){
    vector<Node> post;
    Node ops[LEN];
    int top=-1;//栈顶指针
    FF(i,in.size()){
        Node u=in[i];
        if(u.isop){
            if(u.op=='('){
                ops[++top]=u;//入栈
            }else if(u.op==')'){
                while(top>=0){
                    Node p=ops[top--];
                    if(p.op=='('){
                        break;
                    }else{
                        post.push_back(p);
                    }
                }
            }else{
                while(top>=0 && getPriority(u.op) <= getPriority(ops[top].op)){
                    post.push_back(ops[top--]);//持续出栈直到满足优先级
                }
                ops[++top]=u;//入栈
            }

        }else{
            post.push_back(u);
        }
    }
    //处理剩下的栈
    while(top>=0){
        post.push_back(ops[top--]);
    }
    return post;
}

后缀表达式计算实值

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Node operate(Node &a,Node& b,char op){
    int v;
    switch(op){
    case '+':
        v=a.num+b.num;
        break;
    case '-':
        v=a.num-b.num;
        break;
    case '*':
        v=a.num*b.num;
        break;
    case '/':
        v=a.num/b.num;
        break;
    }
    return Node(v);
}

int calcPostOrderExpress(vector<Node>& post){
    Node s[LEN];
    int top=-1;
    FF(i,post.size()){
        Node& u=post[i];
        if(u.isop){
            Node a=s[top--];
            Node b=s[top--];
            Node ans=operate(a,b,u.op);
            s[++top]=ans;
        }else{
            s[++top]=u;
        }
    }
    return s[0].num;
}

完整代码

复制代码

#include <bits/stdc++.h>
#define FF(a,b) for(int a=0;a<b;a++)
#define F(a,b) for(int a=1;a<=b;a++)
#define LEN 200
#define INF 100000
#define bug(x) cout<<#x<<"="<<x<<endl;

using namespace std;
typedef long long ll;
const double pi=acos(-1);

typedef struct Node{//运算结点，记录数字或运算符号
    bool isop;
    char op;
    int num;
    Node(){}
    Node(int d){
        num=d;
        isop=0;
    }
    Node(char op_){
        op=op_;
        isop=1;
    }
    void output(){
        if(isop) cout<<op;
        else cout<<num;
    }
}Node;

vector<Node> exp2nodes(string exp){
    vector<Node> ans;
    FF(i,exp.size()){
        char c=exp[i];
        if(c>='0' && c<='9'){
            ans.push_back((int)(c-'0'));
        }else{
            ans.push_back(c);
        }
    }
    return ans;
}

void outputNodes(vector<Node>& v){
    FF(i,v.size()){
        v[i].output();
    }
    cout<<endl;
}

void outputOps(Node* ops,int top){
    for(int i=0;i<=top;i++){
        ops[i].output();
    }
    cout<<endl;
}

}else{
            post.push_back(u);
        }
    }
    //处理剩下的栈
    while(top>=0){
        post.push_back(ops[top--]);
    }
    return post;
}

Node operate(Node &a,Node& b,char op){
    int v;
    switch(op){
    case '+':
        v=a.num+b.num;
        break;
    case '-':
        v=a.num-b.num;
        break;
    case '*':
        v=a.num*b.num;
        break;
    case '/':
        v=a.num/b.num;
        break;
    }
    return Node(v);
}

int calcPostOrderExpress(vector<Node>& post){
    Node s[LEN];
    int top=-1;
    FF(i,post.size()){
        Node& u=post[i];
        if(u.isop){
            Node a=s[top--];
            Node b=s[top--];
            Node ans=operate(a,b,u.op);
            s[++top]=ans;
        }else{
            s[++top]=u;
        }
    }
    return s[0].num;
}

int main()
{
    vector<Node> in,post;
    string exp="1+2*3+(4*5+6)*7";
    in=exp2nodes(exp);
    outputNodes(in);
    post=yieldPostOrderExpress(in);
    outputNodes(post);
    bug(  calcPostOrderExpress(post))
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define FF(a,b) for(int a=0;a<b;a++)
#define F(a,b) for(int a=1;a<=b;a++)
#define LEN 200
#define INF 100000
#define bug(x) cout<<#x<<"="<<x<<endl;

using namespace std;
typedef long long ll;
const double pi=acos(-1);

typedef struct Node{//运算结点，记录数字或运算符号
    bool isop;
    char op;
    int num;
    Node(){}
    Node(int d){
        num=d;
        isop=0;
    }
    Node(char op_){
        op=op_;
        isop=1;
    }
    void output(){
        if(isop) cout<<op;
        else cout<<num;
    }
}Node;

vector<Node> exp2nodes(string exp){
    vector<Node> ans;
    FF(i,exp.size()){
        char c=exp[i];
        if(c>='0' && c<='9'){
            ans.push_back((int)(c-'0'));
        }else{
            ans.push_back(c);
        }
    }
    return ans;
}

void outputNodes(vector<Node>& v){
    FF(i,v.size()){
        v[i].output();
    }
    cout<<endl;
}

int getPriority(char op){
    switch(op){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

void outputOps(Node* ops,int top){
    for(int i=0;i<=top;i++){
        ops[i].output();
    }
    cout<<endl;
}

vector<Node> yieldPostOrderExpress(vector<Node> &in){
    vector<Node> post;
    Node ops[LEN];
    int top=-1;//栈顶指针
    FF(i,in.size()){
        Node u=in[i];
        if(u.isop){
            if(u.op=='('){
                ops[++top]=u;//入栈
            }else if(u.op==')'){
                while(top>=0){
                    Node p=ops[top--];
                    if(p.op=='('){
                        break;
                    }else{
                        post.push_back(p);
                    }
                }
            }else{
                while(top>=0 && getPriority(u.op) <= getPriority(ops[top].op)){
                    post.push_back(ops[top--]);//持续出栈直到满足优先级
                }
                ops[++top]=u;//入栈
            }

        }else{
            post.push_back(u);
        }
    }
    //处理剩下的栈
    while(top>=0){
        post.push_back(ops[top--]);
    }
    return post;
}

Node operate(Node &a,Node& b,char op){
    int v;
    switch(op){
    case '+':
        v=a.num+b.num;
        break;
    case '-':
        v=a.num-b.num;
        break;
    case '*':
        v=a.num*b.num;
        break;
    case '/':
        v=a.num/b.num;
        break;
    }
    return Node(v);
}

int calcPostOrderExpress(vector<Node>& post){
    Node s[LEN];
    int top=-1;
    FF(i,post.size()){
        Node& u=post[i];
        if(u.isop){
            Node a=s[top--];
            Node b=s[top--];
            Node ans=operate(a,b,u.op);
            s[++top]=ans;
        }else{
            s[++top]=u;
        }
    }
    return s[0].num;
}

int main()
{
    vector<Node> in,post;
    string exp="1+2*3+(4*5+6)*7";
    in=exp2nodes(exp);
    outputNodes(in);
    post=yieldPostOrderExpress(in);
    outputNodes(post);
    bug(  calcPostOrderExpress(post))
    return 0;
}