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

68 阅读 0 评论 45 点赞

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

概述

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

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;
}

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

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;
}

后缀表达式计算实值

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;
}

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;
}