qq_40241747
木梨moolee
采纳率0%
2018-10-31 08:52 浏览 982

ball ball各位大佬,C语言中序表达式树求值问题

给定一个如(x1+3.25)*(2.8-3.64)*x2的中缀表达式,输出其前中后序,输入数据更新变量的值以后求表达式值。这个怎么实现呀,我只会做全是常量的表达式求值。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答 默认 最新

  • devmiao devmiao 2018-10-31 13:31
     #include<iostream>
    #include<map>
    #include<string>
    #include<stack>
    #include<vector>
    using namespace std;
    class Logic {
    public:
        Logic() {}                                      //构造函数
        void Load(string);                                //input
        int priority(char);                               //获取运算符优先级
        string trans(string);                             //中缀式->后缀式
        double calculate();    //逻辑判断
        void V_assign();                                  //变量赋值
        string M_exp;                            //中缀式
        string P_exp;                            //后缀式
        map<string, double> variate;               //赋值序列
    };
    void Logic::Load(string str) {
        M_exp = str;;
        P_exp = trans(M_exp);             //处理数据(表达式转换)
    }
    int Logic::priority(char ch) {
        if (ch == '*'||ch=='/')
            return 2;
        if (ch == '+'||ch=='-')
            return 1;
        if (ch == '(')
            return -1;
        return 0;
    }
    double Logic::calculate() {
        string operators("+-*/");
        stack<double> res;            //此栈用作运算
        double a, b;
        for (int i = 0; i<P_exp.length(); i++) {
            if (operators.find(P_exp[i]) == string::npos) {      //遇到操作数,根据“字典”翻译后入栈
                res.push(variate[P_exp.substr(i, 1)]);
            }
            else {
                switch (P_exp[i]) {
                case '+':
                    a = res.top();
                    res.pop();
                    b = res.top();
                    res.pop();
                    res.push(a + b);
                    break;
                case '*':
                    a = res.top();
                    res.pop();
                    b = res.top();
                    res.pop();
                    res.push(a * b);
                    break;
                case '-':
                    a = res.top();
                    res.pop();
                    b = res.top();
                    res.pop();
                    res.push(b-a);
                    break;
                case '/':
                    a = res.top();
                    res.pop();
                    b = res.top();
                    res.pop();
                    res.push(b/a);
                    break;
                }
            }
        }
        return res.top();
    }
    string Logic::trans(string m_exp) {
        string p_exp;
        stack<char> stk;
        string operators("+-*/(");
        for (int i = 0; i < m_exp.length(); i++) {
            string one;
            if (operators.find(m_exp[i]) != string::npos) {      //出现操作符
                if (m_exp[i] == '(')         //栈中添加左括号
                    stk.push(m_exp[i]);
                else {                      //操作符的优先级判断
                    while ((!stk.empty()) && (priority(m_exp[i]) <= priority(stk.top()))) {    //当栈不为空时,进行优先级判断
                        p_exp.push_back(stk.top());   //若当前操作符优先级低于栈顶,弹出栈顶,放到后缀式中
                        stk.pop();
                    }
                    stk.push(m_exp[i]);             //将当前操作符入栈
                }
            }
            else if (m_exp[i] == ')') {            //出现右括号时,将栈中元素一直弹出,直至弹出左括号
                while (stk.top() != '(') {
                    p_exp.push_back(stk.top());
                    stk.pop();
                }
                stk.pop();                         //弹出左括号
            }
            else {           //把操作数加入到后缀式中
                variate[m_exp.substr(i, 1)] = 0;
                p_exp.push_back(m_exp[i]);
            }
    
        }
        while (!stk.empty()) {    //将栈中剩余操作符放到后缀式中
            p_exp.push_back(stk.top());
            stk.pop();
        }
        return p_exp;
    }
    void Logic::V_assign() {       //公式赋值
        int i = 0;
        for (auto it = variate.begin(); it != variate.end(); it++) {
            cout << "Enter the " << it->first << " : ";
            cin >> it->second;
        }
    }
    int main() {
        Logic my;
        string str;
        cin >> str;
        my.Load(str);
        cout << "后缀表达式:" << my.P_exp << endl;
        cout << "赋值:" << endl;
        my.V_assign();
        cout<<"结果为:"<<my.calculate();
        return 0;
    }
    
    点赞 1 评论 复制链接分享

相关推荐