[PHP][regexp]Dzielenie wyrażeń arytmetycznych za pomocą wyrażeń regularnych Opcje

[shinuexx]

Witam.
Chciałem sobie zrobić prosty kalkulator który będzie pobierał od użytkownika wyrażenie arytmetyczne i zwracał jego wynik. Np:
Podaję:

Kod

(10+9)/(11*8)

Otrzymuję

Kod

0.215909090

Myślałem nad wykorzystaniem do tego wyrażeń regularnych, ale pojawia się pewien problem. Otóż nie bardzo wiem jak wymusić na kwantyfikatorach, aby dzielił mi wyrażenie tylko względem najwyższego znaku tzn. powyższe wyrażenie powinno mi podzielić na:

Kod

l=(10+9);
r=(11*8);
sign=/;

oczywiście powyższe wyrażenia mogą wyglądać także inaczej. Np można używać na nich prostych funkcji:

Kod

sin(10+4)/cos(8-11)
l=sin(10+4);
sign=/;
r=cos(8-11);

Do tej pory używałem wyrażenia regularnego:

Kod

/^(?<l>[[:print:]]+)(?<sign>[\*\/\-\+]{1})(?<r>[[:print:]]+)/

Każdą ze stron wyrażenia arytmetycznego będę rozpoznawał rekurencyjnie, i do analizy funkcji mam już wyrażenie regularne
Jak można by to najrozsądniej rozwiązać?


Ten post edytował shinuexx 27.11.2011, 14:10:33

[Crozin]

Wyrażenia regularne kompletnie nie nadają się do czegoś takiego, tutaj powinieneś wykorzystać normalny parser wyrażeń matematycznych (taki który najpierw rozbija ciąg na tokeny, a następnie tworzy z nich drzewo wyrażeń):

Kod

sin(10+4)/cos(8-11)

Tokeny:
sin, (, 10, +, 4, ), /, cos, (, 8, -, 11, )

Drzewo wyrażeń:

     "/"
   /      \
sin      cos
  |        |
10 + 4   8 - 11

Dzięki temu będziesz mieć możliwość wyłapywania błędów składni, ustalania pierwszeństwa operatorów itd.

Ten post edytował Crozin 27.11.2011, 14:07:31

[shinuexx]

Czyli analizuję ciąg od początku, sprawdzam co mam a potem czego oczekuję następnie. Jeśli tak nie jest to błąd a jeśli jest to następny znak?

[Crozin]

Pogoogleaj sobie za "writing parser c / java" czy coś w ten deseń. Jest masa materiałów, całość nie jest trudna (szczególnie gdy mówimy o wyrażeniach matematycznych) ale dosyć obszerna.
Ewentualnie jak z czymś konkretnym będziesz mieć problem, pytaj.

[shinuexx]

W sumie to nie bardzo już teraz wiem co miałem znaleźć. O LEXER'ach i PARSER'ach??

ok. Dowiedziałem się od znajomego, że można to zrobić za pomocą odwrotnej notacji polskiej. Jak dla mnie jest to naprawdę przyjemny i przejrzysty algorytm liczenia wyrażeń matematycznych uwzględniający pierwszeństwo. Wyrażeń regularnych użyłem do dzielenia ciągu na tokeny.

[PHP] pobierz, plaintext 
public function _lexer(){
        if(!preg_match_all("/([[:digit:]]+[e|E]{1}[\+\-]{0,1}[[:digit:]]+|[A-Za-z]{1}[A-Za-z0-9\_]*|[[:digit:]]+[\.]{0,1}[[:digit:]]*|[\.]{1}[[:digit:]]+|[\!\(\)\+\-\^\/\*\[\]]{1})/",$this->_input,$m))
            return false;
        $this->_token=$m[0];
        return true;
    }
[PHP] pobierz, plaintext 

Nie miałem innego pomysłu na token'owanie a to było dość przyjemne. Jeśli ktoś miałby lepszy pomysł to nie mam nic lepszego.
Jeśli ktoś chce mogę zamieścić kody tego co do tej pory udało mi się zrobić tj:
-lexer,
-parser,
-counter,
wraz z obsługą podstawowych funkcji oraz podstawiania zmiennych zdefiniowanych przed wyliczeniem. Brak jeszcze obsługi błędów, co zamierzam wprowadzić.

[Crozin]

Nie miałem innego pomysłu na token'owanie a to było dość przyjemne. Jeśli ktoś miałby lepszy pomysł to nie mam nic lepszego.

Generalnie użycie wyr. reg. nawet do wydzielenia tokenów jest błędne - bo one wyłapią jedynie pewne wzorce, a nie zwrócą rezultatu pełnej analizy ciągu (jeżeli coś nie będzie pasować to to ominą zamiast rozpoznać jako niewłaściwy token).
Nie mniej jednak jeżeli spełnia to swoje zadanie w zadowalającym stopniu możesz to tak zostawić.

[shinuexx]

No tak. Ale jeśli podczas dalszego parserowania wyrażenia znajdzie błąd (brak operatora itp.) to jestem w stanie znaleźć błąd występujący w składni.

Nawet jeśli miałbym coś innego użyć do tokenowania to co to miałoby być i jak miałbym tego użyć

[Crozin]

Kod

3 + #23

Przy pomocy wyrażeń otrzymasz 3, +, 23 podczas gdy powinieneś otrzymać błąd - wdarł się # przez który na dobrą sprawę nie wiadomo co tak na prawdę powinno się zrobić.

Nawet jeśli miałbym coś innego użyć do tokenowania to co to miałoby być i jak miałbym tego użyć

Odczytujesz znak po znaku otrzymany ciąg, wyciągając z niego kolejne elementy. W sieci jest od groma różnego rodzaju parserów (bibliotek) więc łatwo można podejrzeć w jaki sposób napisać całość (pewnie nawet gotowca można znaleźć).

[shinuexx]

czyli

Czyli analizuję ciąg od początku, sprawdzam co mam a potem czego oczekuję następnie. Jeśli tak nie jest to błąd a jeśli jest to następny znak?

Bo jak narazie stworzyłem coś takiego:

[PHP] pobierz, plaintext 
<?php
 
/**
 * @author ShInUeXx
 * @copyright 2011
 */
 
class math_exp{
 
    /**
     * 
     * Typy operatorów
     * 
     */
    const T_POW="^";
    const T_MUL="*";
    const T_DIV="/";
    const T_ADD="+";
    const T_MIN="-";
    CONST T_LPAR="(";
    CONST T_RPAR=")";
    CONST T_FACT="!";
 
    const I_NUM=0;
    const I_OPR=1;
    const I_FUN=2;
    const I_VAR=3;
 
    private $_opr=array(
        self::T_POW,
        self::T_MUL,
        self::T_DIV,
        self::T_ADD,
        self::T_MIN,
        self::T_FACT,
    );
 
    private $_allowed_function=array(
        "abs",
        "acos",
        "acosh",
        "asin",
        "asinh",
        "atan2",
        "atan",
        "atanh",
        "ceil",
        "cos",
        "cosh",
        "exp",
        "floor",
        "fmod",
        "log10",
        "ln",
        "rand",
        "round",
        "sin",
        "sinh",
        "sqrt",
        "tan",
        "tanh",
    );
 
    private $_vars=array();
    private $_token=array();
    private $_input;
    private $_result=array();
    private $_output;
 
    public function __construct($vars=array()){
        $this->_vars=$vars;
    }
 
    public function addExp($str){
        $this->_input=$str;
    }
 
    public function addVars($vars){
        $this->_vars=array_merge($this->_vars,$vars);
    }
 
    private function _priority($n){
        switch($n){
            case self::T_MIN:return 0;break;
            case self::T_ADD:return 0;break;
            case self::T_DIV:return 1;break;
            case self::T_MUL:return 1;break;
            case self::T_POW:return 2;break;
            case self::T_FACT:return 3;break;
            case null:return -1;break;
            default:
                return getrandmax();
            break;
        }
    }
 
    public function countExp($str=null){
        if($str===null)$str=$this->_input;
        $this->addExp($str);
        if(!$this->_lexer()) return false;
        $this->_reverse_polish_notation();
        $this->_count();
        return $this->_output;
    }
 
    public function _lexer(){
        if(!preg_match_all("/([[:digit:]]+[e|E]{1}[\+\-]{0,1}[[:digit:]]+|[A-Za-z]{1}[A-Za-z0-9\_]*|[[:digit:]]+[\.]{0,1}[[:digit:]]*|[\.]{1}[[:digit:]]+|[\!\(\)\+\-\^\/\*\[\]]{1})/",$this->_input,$m))
            return false;
        $this->_token=$m[0];
        return true;
    }
 
    public function _identify($token){
        if(is_numeric($token))
            return self::I_NUM;
        elseif(in_array($token,($this->_opr)))
            return self::I_OPR;
        elseif(in_array($token,$this->_allowed_function))
            return self::I_FUN;
        else
            return self::I_VAR;
    }
 
    public function _reverse_polish_notation(){
        $return=&$this->_result;
        $token=$this->_token;
        $stack=array();
        foreach($token as $k=>$v){
            $pr=$this->_priority($v);
            if($v==self::T_LPAR){
                $stack[]=$v;
                $sel=1;
            }
            elseif($v==self::T_RPAR){
                $par=array_pop($stack);
                while($par!=self::T_LPAR){
                    $return[]=$par;
                    $par=array_pop($stack);
                }         
            }
            elseif($this->_identify($v)==self::I_NUM||$this->_identify($v)==self::I_VAR){
                $return[]=$v;
            }
            elseif($this->_identify($v)==self::I_OPR||$this->_identify($v)==self::I_FUN){
                $last=array_pop($stack);
                $T=$this->_priority($last);
                if($pr>$T){
                    if($last!==null) {
                        $stack[]=$last;
                    };
                    $stack[]=$v;
                }
                elseif($last==self::T_LPAR){
                    if($v=='-'&&($k==0||$token[$k-1]==self::T_LPAR))$return[]="0";
                    $stack[]=$last;
                    $stack[]=$v;
                }
                else{
                    if($last!==null&&$last!=self::T_LPAR) $return[]=$last;
                    $stack[]=$v;
                }
            }
        }
        while(!empty($stack))
            $return[]=array_pop($stack);
 
    }
 
    public function _count(){
        $vars=$this->_vars;
        $rpn=$this->_result;
        $stack=array();
        foreach($rpn as $v){
            switch($this->_identify($v)){
                case 0:
                    $stack[]=$v;
                break;
                case 1:
                    switch($v){
                        case "*":
                            $b=array_pop($stack);
                            $a=array_pop($stack);
                            $stack[]=$a*$b;
                        break;
                        case "^":
                            $b=array_pop($stack);
                            $a=array_pop($stack);
                            $stack[]=pow($a,$b);
                        break;
                        case "/":
                            $b=array_pop($stack);
                            $a=array_pop($stack);
                            $stack[]=$a/$b;
                        break;
                        case "+":
                            $b=array_pop($stack);
                            $a=array_pop($stack);
                            $stack[]=$a+$b;
                        break;
                        case "-":
                            $b=array_pop($stack);
                            $a=0;
                            if($this->_identify(end($stack))==0)
                                $a=array_pop($stack);
                            $stack[]=$a-$b;
                        break;
                        case "!":
                            $a=array_pop($stack);
                            $stack[]=factorial($a);
                        break;
                        default:
 
                        break;
                    }
                break;
                case 2:
                    $a=array_pop($stack);
                    $stack[]=call_user_func($v,$a);
                break;
                case 3:
                    $stack[]=$vars[$v];
                break;
            }
        }
        $this->_output=array_pop($stack);
    }   
}
 
?>
[PHP] pobierz, plaintext 

i na większości wyrażeń działa (oczywiście jeszcze błędów nie obsługuje)

[Crozin]

Czyli analizuję ciąg od początku, sprawdzam co mam a potem czego oczekuję następnie. Jeśli tak nie jest to błąd a jeśli jest to następny znak?

Mógłbyś już nawet na etapie wykrywania tokenów wywalać pewne błędy składni, np. ")" nie może się pojawić jeżeli nie ma poprzedzającego go "(", ale generalnie darowałbym sobie na tym etapie takie coś. Nie możesz przewidzieć wszystkich w tym miejscu, w dodatku "zabrudziłbyś" kod tokenizera.

1. Odczytujesz wszystkie tokeny, nie bacząc na ich poprawność względem gramatyki języka (tutaj: wyrażeń matematycznych).
2. Na podstawie odczytanych tokenów próbujesz utworzyć AST. Na tym etapie wyłapujesz błędy składni.

EDIT:
Nie analizowałem całości ale kilka błędów już rzuciło mi się w oczy:
1. "-" (minus) to nie tylko operator odejmowania (operator dwuargumentowy), ale i operator wskazujący na wartość przeciwną (ujemną) następującego po nim wyrażenia (operator jednoargumentowy), np.: $a = -$b;
2. W przypadku gdy będziesz miał zapis 2 + invalidFunction(6) w chwili obecnej parser potraktuje invalidFunction jako... zmienną. Nie muszę chyba tłumaczyć, że jest to bzdura.

EDIT:
Na prawdę polecam poświęcić ze dwie godz nad wynikami wyszukiwania c / java / php math parser (język jest tutaj bez znaczenia) - jest tego sporo

Ten post edytował Crozin 29.11.2011, 00:45:21

[shinuexx]

Co do minusa to podam RPN z przykładowych wyrażeń tworzy takie:

Kod

-3*(-6)
=
3 0 6 - * -
-----------------
(-3)*(-6)
=
0 3 - 0 6 - *
-----------------
(2-3)*(1-6)
=
2 3 - 1 6 - *
-----------------
-1-1
=
1 - 1 -

także myślę że z tym sobie poradzi.
Postaram się poczytać o parserach coś więcej.