web-gelistirme-sc.com

c ++ ile matematik ifadesinin ayrıştırılması

Ağaçları Ayrıştırma hakkında bir sorum var:

Bir dizgem var (matematik ifadesi tahmini), örneğin: (a+b)*c-(d-e)*f/g. Bu ifadeyi bir Ağaçta ayrıştırmam gerekiyor:

class Exp{};
class Term: public Exp{
    int n_;
}

class Node: Public Exp{
    Exp* loperator_;
    Exp* roperator_;
    char operation; // +, -, *, /
}

Yukarıdaki ifade dizesini temsil eden bir ağaç oluşturmak için hangi algoritmayı kullanabilirim?

23
Hal Nuevemil

Shunting-yard algoritmasını kullanın. Wikipedia açıklaması oldukça kapsamlı, umarım yeterli olacaktır.

Ayrıca resmi bir dilbilgisi yazmayı da deneyebilirsiniz, örneğin a ayrıştırma ifadesi dilbilgisiPEG'ler hakkında bu site , PEG ayrıştırma için 3 C/C++ kütüphanesini listeler.

10
Kos

(a+b)*c-(d-e)*f/g bir düzeltme ifadesidir. 

Kolayca tree yapmak için, bunu önce bir Önek ifadesine dönüştürün.

Örnekten, __. (A * B) + (C / D) öneki + (* A B) (/ C D)

     (+)            
     / \        
    /   \       
  (*)    (/)         
  / \   /  \        
 A   B C    D   

 ((A*B)+(C/D))  

Ağacınız daha sonra kök düğümü olarak + işaretine sahip. Her operatör hakkında sol ve sağ alt ağacı doldurmaya devam edebilirsiniz.

Ayrıca, bu bağlantı Özyinelemeli İniş Ayrıştırmayı ayrıntılı olarak açıklar ve uygulanabilir.

5

İlk adım, ifadeleriniz için bir gramer yazmak. Böyle basit bir durum için ikinci adım, özyinelemeli bir iniş çözümleyici yazmaktır, bu benim önereceğim algoritma. İşte iyi görünümlü bir C uygulaması olan özyinelemeli iniş ayrıştırıcıların wiki sayfası.

http://en.wikipedia.org/wiki/Recursive_descent_parser

4
jahhaj
#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
#include <iterator>

using namespace std;

class Exp{
public:
//  Exp(){}
    virtual void print(){}
    virtual void release(){}
};
class Term: public Exp {
    string val;
public:
    Term(string v):val(v){}
    void print(){
        cout << ' ' << val << ' ';
    }
    void release(){}
};

class Node: public Exp{
    Exp *l_exp;
    Exp *r_exp;
    char op; // +, -, *, /
public:
    Node(char op, Exp* left, Exp* right):op(op),l_exp(left), r_exp(right){}
    ~Node(){
    }
    void print(){
        cout << '(' << op << ' ';
        l_exp->print();
        r_exp->print();
        cout  << ')';
    }
    void release(){
        l_exp->release();
        r_exp->release();
        delete l_exp;
        delete r_exp;
    }
};

Exp* strToExp(string &str){
    int level = 0;//inside parentheses check
    //case + or -
    //most right '+' or '-' (but not inside '()') search and split
    for(int i=str.size()-1;i>=0;--i){
        char c = str[i];
        if(c == ')'){
            ++level;
            continue;
        }
        if(c == '('){
            --level;
            continue;
        }
        if(level>0) continue;
        if((c == '+' || c == '-') && i!=0 ){//if i==0 then s[0] is sign
            string left(str.substr(0,i));
            string right(str.substr(i+1));
            return new Node(c, strToExp(left), strToExp(right));
        }
    }
    //case * or /
    //most right '*' or '/' (but not inside '()') search and split
    for(int i=str.size()-1;i>=0;--i){
        char c = str[i];
        if(c == ')'){
            ++level;
            continue;
        }
        if(c == '('){
            --level;
            continue;
        }
        if(level>0) continue;
        if(c == '*' || c == '/'){
            string left(str.substr(0,i));
            string right(str.substr(i+1));
            return new Node(c, strToExp(left), strToExp(right));
        }
    }
    if(str[0]=='('){
    //case ()
    //pull out inside and to strToExp
        for(int i=0;i<str.size();++i){
            if(str[i]=='('){
                ++level;
                continue;
            }
            if(str[i]==')'){
                --level;
                if(level==0){
                    string exp(str.substr(1, i-1));
                    return strToExp(exp);
                }
                continue;
            }
        }
    } else
    //case value
        return new Term(str);
cerr << "Error:never execute point" << endl;
    return NULL;//never
}

int main(){
    string exp(" ( a + b ) * c - ( d - e ) * f / g");
    //remove space character
    exp.erase(remove_if(exp.begin(), exp.end(), ::isspace), exp.end());
    Exp *tree = strToExp(exp);
    tree->print();
    tree->release();
    delete tree;
}
//output:(- (* (+  a  b ) c )(/ (* (-  d  e ) f ) g ))
3
BLUEPIXY

İfadenizi oluşturmak için bu dilbilgisini kullanabilirsiniz.

exp:
    /* empty */
  | non_empty_exp { print_exp(); }
  ;
non_empty_exp:
    mult_div_exp
  | add_sub_exp
  ;
mult_div_exp:
    primary_exp
  | mult_div_exp '*' primary_exp { Push_node('*'); }
  | mult_div_exp '/' primary_exp { Push_node('/'); }
  ;
add_sub_exp:
    non_empty_exp '+' mult_div_exp { Push_node('+'); }
  | non_empty_exp '-' mult_div_exp { Push_node('-'); }
  ;
primary_exp:
  | '(' non_empty_exp ')'
  | NUMBER { Push_term($1); }
  ;

Ve lexer için aşağıdaki.

[ \t]+   {}
[0-9]+   { yylval.number = atoi(yytext); return NUMBER; }
[()]     { return *yytext; }
[*/+-]   { return *yytext; }

İfade, bu yordamları kullanarak, giderken oluşturulur:

std::list<Exp *> exps;

/* Push a term onto expression stack */
void Push_term (int n) {
    Term *t = new Term;
    t->n_ = n;
    exps.Push_front(t);
}

/* Push a node onto expression stack, top two in stack are its children */
void Push_node (char op) {
    Node *n = new Node;
    n->operation_ = op;
    n->roperator_ = exps.front();
    exps.pop_front();
    n->loperator_ = exps.front();
    exps.pop_front();
    exps.Push_front(n);
}

/*
 * there is only one expression left on the stack, the one that was parsed
 */
void print_exp () {
    Exp *e = exps.front();
    exps.pop_front();
    print_exp(e);
    delete e;
}

Aşağıdaki yordam, ifade ağacınızı güzel şekilde yazdırabilir:

static void
print_exp (Exp *e, std::string ws = "", std::string prefix = "") {
    Term *t = dynamic_cast<Term *>(e);
    if (t) { std::cout << ws << prefix << t->n_ << std::endl; }
    else {
        Node *n = dynamic_cast<Node *>(e);
        std::cout << ws << prefix << "'" << n->operation_ << "'" << std::endl;
        if (prefix.size()) {
            ws += (prefix[1] == '|' ? " |" : "  ");
            ws += "  ";
        }
        print_exp(n->loperator_, ws, " |- ");
        print_exp(n->roperator_, ws, " `- ");
    }
}
3
jxh

Bunu gün içinde halletmek için bir sınıf yazdım. Biraz ayrıntılı ve belki de gezegendeki en verimli şey değil, ancak işaretli/imzasız tamsayıları, çift, yüzer, mantıksal ve bitli işlemleri gerçekleştirir.

Sayısal taşma ve aşağı akış tespit eder, açıklayıcı metin ve sözdizimi ile ilgili hata kodlarını döndürür, tam sayılar olarak çiftleri işlemeye zorlanabilir veya tabelaları görmezden gelebilir, kullanıcı tanımlı kesinlik ve akıllı yuvarlamayı destekler ve DebugMode (true) ayarladıysanız bile çalışmasını gösterir.

Son olarak ...... herhangi bir harici kütüphaneye güvenmiyor, bu yüzden bırakabilirsin.

Örnek kullanım:

CMathParser parser;

double dResult = 0;
int iResult = 0;

//Double math:
if (parser.Calculate("10 * 10 + (6 ^ 7) * (3.14)", &dResult) != CMathParser::ResultOk)
{
    printf("Error in Formula: [%s].\n", parser.LastError()->Text);
}
printf("Double: %.4f\n", dResult);

//Logical math:
if (parser.Calculate("10 * 10 > 10 * 11", &iResult) != CMathParser::ResultOk)
{
    printf("Error in Formula: [%s].\n", parser.LastError()->Text);
}
printf("Logical: %d\n", iResult);

En son sürüm, CMathParser GitHub Repository aracılığıyla her zaman kullanılabilir.

1
NTDLS