Shunting-yard algoritmi!

Algoritm nomini inglizcha holatida keltirdim. Chunki ayrim atamalarni internetdan inglizcha qidirib topish osonroq. Algoritm o'zbekchada "Saralash stansiyasi" deb nomlanadi! Bu nomni temir yo'llardagi poyezdlarni saralaydigan joyga o'xshaganligi uchun bo'lsa kerak.

Algoritm maqsadi, matematik ifodalarni kompyuter yordamida tez hisoblashdir.

Misol uchun: 5 * (cos(1) ^ 2 + sin(1) ^ 2) / 2 + 10 - 3 ^ 2 + max(sqrt(25), sqrt(36))
Ushbu ifoda qiymati: 9.5 ga teng. 5 * 1 / 2 + 10 - 9 + 6 = 9.5

Algoritm bir qarashda murakkab ko'rinadi, lekin aslida juda oson va qulay qilib o'ylab topilgan.

Algoritmni tushuntirishdan oldin bir matematikaga nazar solsak. Biz bilamizki, matematikada + (qo'shish), - (ayirish) amallari * (ko'paytirish) va / (bo'lish) amallaridan keyin bajariladi. Lekin qo'shish va ayirish, ko'paytirish va bo'lishlar teng kuchli hisoblanadi va chap tarafdan boshlab hisoblanadi.

    Misol uchun: 5 + 4 * 3 / 2 - 1 = 10

Matematik amallar bilan birga yana qavslar ham qo'llaniladi. Qavslar hamma bilgandek oldin qavs ichi keyin tashqarisi hisoblanadi. Funksiyalar ham qavslar kabi, qavs ichi hisoblangandan keyin funksiya qiymati hisoblanadi.

    Misol uchun: 2 * (1 + 3) + sqrt(9 + 16) = 13

Bulardan tashqari darajaga ko'tarish, yuqoridagi amallarga qaraganda boshqacharoq ya'ni o'ng tarafdan boshlab hisoblab kelinadi.

    Misol uchun: 2 ^ 3 ^ 2 = 512
Ko'pchilik kalkulyatorlar 64 ya'ni (2 ^ 3) ^ 2 ko'rinishida hisoblaydi. Bu noto'g'ri! Aslida yuqoridagi ifoda 2 ^ (3 ^ 2) ko'rinishida bo'lishi kerak.

E'tibor bergan bo'lsangiz, matematik amallarda ustunlik mavjud. Ya'ni qaysi amal, qaysi amaldan oldin va qay tartibda bajarilishi matematikada ma'lum. Ushbu algoritm ham shu qoidaga amal qilgan holda quyidagi shartlarni kiritadi:

Operator Ustunlik Hisoblash tartibi
^ 4 O'ng
* 3 Chap
/ 3 Chap
+ 2 Chap
- 2 Chap
( -1 -

Ushbu qoida, keyinchalik RPN ( Reverse Polish notation) ifodani hisoblash uchun kerak bo'ladi.

RPN bu - matematik ifoda bo'lib, operator qiymatlari har doim o'zidan oldin keladi.
Misol uchun:
3 + 4 ning RPN da yozilishi: 3 4 +.
3 + 4 * 2 ning RPN da yozilishi: 3 4 2 * +

Bu nimaga kerak deysizmi? RPN da yozilgan ifodani kompyuter yordamida qiymatini chiqarish juda oson. Bunga hozir boshni achitmaylikda, matematik ifodadan RPN hosil qilishni o'rganaylik. Shundan keyin o'zingiz tushunib olasiz, qanchalik qulay narsa ekanligini.

Ayrim atamalarni ingliz tilida keltirdim, chunki man keltirgan koddayam shu so'zlar ishlatilgan.

TOKEN - bu matematik ifodadagi son, funksiya, funksiya parametrlarni ajratuvchi belgi (ya'ni vergul), operator yoki qavs bo'lishi mumkin bo'lgan obyekt.

OUTPUT QUEUE - bu chiqish navbati (ya'ni oddiy massiv bo'lib, barcha turdagi TOKEN larni o'zida saqlaydi. Umuman olganda shu QUEUE dagi ketma-ketlik RPN ifodani hosil qiladi)

OPERATOR STACK - bu operatorlarni (ya'ni son bo'lmagan TOKEN larni saqlaydi)

Tushunmadingizmi, GOTO TOP!

RPN ifodasini yasash algoritmi ( pseudocode):

while true:
    TOKEN = readToken()
    [1] agar TOKEN = NULL bo'lsa:
        break
    [2] agar TOKEN son bo'lsa:
        OUTPUT QUEUE ga TOKEN ni qo'shimiz
    [3] agar TOKEN funksiya bo'lsa:
        OPERATOR STACK ga TOKEN ni qo'shamiz
    [4] agar TOKEN vergul bo'lsa: //bu funksiya parametrlarini ajratuvchi belgi
        OPERATOR STACK ning yuqorisidagi qiymatlarini to '(' qavs uchragunga qadar (pop qilib) OUTPUT QUEUE ga qo'shamiz. Agar OPERATOR STACK da '(' belgi uchramasa matematik ifoda not'g'ri berilgan bo'ladi.
    [5] agar TOKEN operator bo'lsa (op1): //ya'ni *,-,+,/,^
        [5.1] - agar OPERATOR STACK da qiymat bo'lsa va uning yuqorisi (top) da turgan TOKEN (op2), va
            op1 chap tarafdan hisoblanadigan operator bo'lsa va uning ustunligi op2 ning ustunligidan kichik yoki teng bo'lsa,
            yoki op1 o'ng tarafdan hisoblanadigan operator bo'lsa va uning ustunligi op2 ning ustunligidan kichik bo'lsa:
            to ushbu qoida bajarilmay qolguncha OPERATOR STACK ning yuqorisigi qiymatini (pop qilib) OUTPUT QUEUE ga o'tkazamiz.
        [5.2] va oldingi shartni bajarib bo'lib TOKEN ni OPERATOR STACK ga qo'shamiz
    [6] agar TOKEN ochiq qavs '(' bo'lsa:
        OPERATOR STACK ga TOKEN ni qo'shamiz
    [7] agar TOKEN yopiq qavs ')' bo'lsa:
        [7.1] - OPERATOR STACK ning yuqorisidagi qiymatlarini to '(' qavs uchragunga qadar (pop qilib) OUTPUT QUEUE ga qo'shamiz.
        [7.2] - OPERATOR STACK dan '(' qavsni chiqarib tashlaymiz (pop)
        [7.3] - '(' ni chiqargandan keyin OPERATOR STACK ning yuqorisidagi TOKEN funksiya bo'lsa uniyam OPERATOR STACK dan o'chirib OUTPUT QUEUE ga qo'shamiz
        [7.4] - Agar OPERATOR QUEUE da '(' yopiq qavs uchramasa, demak ifoda noto'g'ri
[8] Agar readToken() NULL qaytarsa:
    [8.1] - agar OUTPUT STACK ning yuqorisida '(' qavs turgan bo'lsa, demak ifoda noto'g'ri
    [8.2] - hammsi to'g'ri bo'lsa va OPERATOR STACK da ma'lumot mavjud bo'lsa, ularning barchasini yuqorisidan boshlab (pop qilib) OUTPUT STACK ga o'tkazamiz.
Tamom

Keling endi yuqorida yozilgan algoritmni, C++ da ko'rib chiqsak (kod C++11 da yozilgan).

Kodlarga o'tishda oldin:

#define NewToken(T) std::make_shared<Token>(T)
typedef std::shared_ptr<Token> SharedToken;
typedef std::vector<SharedToken> TokenVector;
typedef std::stack<SharedToken> TokenStack;

bu yangi tiplar, kod yozishni va kodning o'qilishini osonlashtirish uchun qilingan.

Birinchi biz TOKEN turlarini aniqlashimiz kerak:

enum TokenTypes {
    NUMBER = 1,
    FUNCTION = 2,
    OPERATOR = 3
};

Endi TOKEN obyektining o'zini yaratamiz.

class Token
{
    //sonlarni saqlash uchun
    double number_;
    //funksiyalarni saqlash uchun
    std::string function_;
    //operatorlarni saqlash uchun
    char op_;
    //Token qayti turga tegishli ekanligini aniqlash uchun
    TokenTypes type_;
    //bular yuqorida keltirilgan ustunliklar jadvali
    static std::map< char, int > op_precedence_;
public:
    Token(double n): number_(n) {type_ = NUMBER;}
    Token(std::string f): function_(f) {type_ = FUNCTION;}
    Token(char c): op_(c) {type_ = OPERATOR;}
    bool isOperator() { return type_ == OPERATOR; }
    bool isFunction() { return type_ == FUNCTION; }
    bool isNumber() { return type_ == NUMBER; }
    //ushbu funksiya qaysi matematik operator o'ng tarafdan boshlab hisoblanishini
    //aniqlash uchun qo'llaniladi. Bizning holatda faqat darajaga ko'tarish
    //o'ng tarafdan bo'lgani uchun shu holat ko'rsatilgan
    bool isRightAssociativity() { return isOperator() && getOperator() == '^'; }
    double getNumber() { return number_; }
    std::string getFunction() { return function_; }
    char getOperator() { return op_; }
    TokenTypes getType() const { return type_; }
    //bu agar token operator bo'lsa
    //uning ustunligini qaytaradi
    int precedence() const {
        if (type_ != OPERATOR)
            return -1;
        return op_precedence_[op_];
    };
    std::string string() {
        if (isFunction())
            return function_;
        if (isOperator())
            return std::string(1, op_);
        if (isNumber())
            return std::to_string(number_);
        return "";
    }
};
//ustunlik jadvalini kiritish
std::map<char, int> Token::op_precedence_ = {
    {'(', -1},
    {'+', 2},
    {'-', 2},
    {'*', 3},
    {'/', 3},
    {'^', 4}
};

Agar yuqoridagi Token obyekti tushunarli bo'lsa, endi RpnExpression nomli obyektga o'tamiz. Bu obyekt bizda OUTPUT QUEUE vazifasini bajaradi.

class RpnExpression
{
    //OUTPUT QUEUE
    TokenVector stack_;
public:
    //OUTPUT QUEUE ga TOKEN qo'shish
    void push (SharedToken t) {
        stack_.push_back (t);
    }
    //OUTPUT QUEUE dan TOKEN olish
    SharedToken pop () {
        SharedToken t = stack_.front ();
        stack_.erase (stack_.begin ());
        return t;
    }
    //OUTPUT QUEUE bo'shligini tekshirish
    bool empty () const { return stack_.empty (); }
    //OUTUPT QUEUE ni chiqarish
    void print() {
        for(auto k : stack_) {
            std::cout<<k->string()<<" ";
        }
        std::cout<<std::endl;
    }
};

Bu obyektda ham tushunarsiz narsa deyarli yo'q! Ya'ni OUTOUT QUEUE ni obyekt ko'rinishiga o'tkazdik xolos.

Shu bilan yordamchi obyektlar tugadi, endi eng asosiy obyekt ya'ni ShuntingYard obyektiga o'tamiz.

O'qish qiyin bo'lmasligi uchun, barcha izohlarni kod ichida keltirdim va algoritmdagi raqamlarga bog'ladim.

class ShuntingYard {
    //bu matematik ifodani saqlaydi: 4 + 2 * 3
    std::string expr_;
    //Bu bizning OUTPUT QUEUE
    RpnExpression rpn_;
    //Bu OPERATOR STACK
    TokenStack op_stack_;
    //Bu ochiq qavslarni OPERATOR STACK ga qo'shadi
    //ya'ni [6]-shart bajarilsa chaqiriladi
    void handle_left_paren () {
        op_stack_.push (NewToken('('));
    }
    //bu yopiq qavs kelganda chaqiriladi
    //ya'ni [7] shart bajarilganda chaqiriladi
    void handle_right_paren () {
        //OPERATOR STACK yuqorisidagi TOKEN '(' bo'lgunga qadar
        //OUTPUT QUEUE ga qo'shamiz
        //ya'ni 7.1 ni bajaryabmiz
        while (!op_stack_.empty() && op_stack_.top ()->getOperator() != '(') {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        //Agar ochiq qavs uchramasa
        //[7.4] ni bajaryapmiz
        if (op_stack_.empty())
            throw std::domain_error("Ifoda noto'g'ri kritilgan");
        // '(' ochilgan qavsni chiqarib tashlaymiz
        // ya'ni [7.2] ni bajaryabmiz
        op_stack_.pop ();
        //Agar eng yuqorisidagi funksiya bo'lsa
        //TOKEN ni OUTPUT QUEUE ga o'tkazamiz
        //ya'ni [7.3] ni bajaryabmiz
        if (op_stack_.top()->isFunction()) {
            rpn_.push(op_stack_.top());
            op_stack_.pop();
        }
    }
    //Agar funksiya parametri bo'luvchisi (vergul) kelsa
    //ya'ni [4]-shart bajarilsa chaqiriladi
    void handle_func_seperator() {
        //ochiq qavs uchragunga qadar OUTPUT QUEUE ga o'tkazamiz, OPERATOR STACK dan
        while (!op_stack_.empty() && op_stack_.top ()->getOperator() != '(') {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        //ifoda not'g'ri, chunki qavs ochilmagan
        if (op_stack_.empty())
            throw std::domain_error("Ifoda noto'g'ri kiritilgan");
    }
    //operator bo'lganda chaqiriladi
    //[5]-shart bajarilsa
    void handle_op(SharedToken t) {
        //agar OPERATOR STACK da qiymat bo'lsa
        //5.1 - qoida
        while(!op_stack_.empty() && ((!t->isRightAssociativity() && t->precedence() <= op_stack_.top()->precedence() /* 1-shart */) ||
              (t->isRightAssociativity() && t->precedence() < op_stack_.top()->precedence()) /* 2-shart */)) {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        //Tokenni OPERATOR STACK ga qo'shamiz
        //5.2
        op_stack_.push(t);
    }
public:
    //Bu RpnExpression ifodani hisoblab bo'lib qaytaradi
    RpnExpression getRpn() {
        //char * ko'rinishiga o'tkazamiz
        //sababi o'qish osonlashadi
        const char* token = expr_.c_str();
        //token bu POINTER *token bu expr_ ning bir BYTE qiymati
        while(token && *token) {
            //bu yerda *token qiymati space (probel, bo'shliq bo'lsa)
            while(*token && isspace(*token)) {
                ++token; //keyingi belgiga o'tamiz
            }
            //agar son kelib qolsa
            //[2]-shart bajarilganda
            if (isdigit(*token)) {
                //token POINTER dan barcha raqamlarni o'qib,
                //double tipiga o'tkazib OUTPUT QUEUE ga TOKEN ni
                //qo'shamiz
                char *next_token;
                rpn_.push(NewToken(strtod(token, &next_token)));
                token = next_token;
            }
            //Agar harf kelib qolsa, demak funksiya
            //[3]-shart bajarilganda
            else if (isalpha(*token)) {
                std::stringstream func;
                do {
                    func<<*token;
                    ++token;
                }while(isalpha(*token));
                //va funksiyani OPERATOR STACK ga qo'shamiz
                op_stack_.push(NewToken(func.str()));
            } else {
                //funksiya bo'lmasa, son bo'lmasa
                //bitta belgini olib
                char op = *token;
                switch(op) {
                    case '(': //[6]-shart
                        handle_left_paren();
                        break;
                    case ')'://[7]-shart
                        handle_right_paren();
                        break;
                    case ','://[4]-shart
                        handle_func_seperator();
                        break;
                    default://qolgan holatlarda
                        handle_op(NewToken(op));
                        break;
                }
                ++token;
            }
        }
        //expr_ ni o'qib bo'lgandan keyin, OPERATOR STACK da qiymat bo'lsa
        //[8]-shart
        //[8.1]-shart
        if (!op_stack_.empty()) {
            if (op_stack_.top()->getOperator() == '(')
                std::domain_error("Ifoda noto'g'ri");
        }
        //[8.2]-shart
        while (! op_stack_.empty ()) {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        return rpn_;
    }
public:
    ShuntingYard(const std::string &expr):
    expr_(expr) {
    }
};

Agar ushbu kodni

ShuntingYard shunting("3 + 4 * 2");
auto rpn = shunting.getRpn();
rpn.print();

ko'rinishida ishlatib ko'rsangiz, sizga dastur ifodaning RPN qiymatini qaytaradi: 3 4 2 * +

Ho'sh, bu nimaga kerak deysizmi yana? Endi RPN dan foydalanib matematik ifodani qanchalik oson hisoblash mumkinligini tushuntirsam.

RPN ifoda double massiv (std::stack<double>)
3 4 2 * +
4 2 * + 3
2 * + 4 3
* + 2 4 3
+ (2 * 4) 3
(2 * 4) + 3

Algoritmi quyidagicha:

[1] rpn yuqorisidagi qiymatini olamiz (pop) (jarayon takrorlanadi)
    [1.1] agar son bo'lsa double massiv ga qo'shamiz (push)
    [1.2] agar operator bo'lsa
        [1.2.1] operator yoki funksiya nechta qiymat olishiga qarab double massiv dan qiymat olamiz (pop)
        [1.2.2] shu olingan qiymatlarni hisoblab yana double massivga qo'shib qo'yamiz (push)
    [1.2] oxirida massiv ning birinchi elementidagi qiymatini chiqaramiz

Va nihoyat kodimizning oxirgi obyektni yan RPN qiymatni hisoblaydigan Calculator obyektiga yetib keldik.

class Calculator {
    //bu double array, qiymatlar shunda saqlanadi
    std::stack< double > operands_;
    //qiymat chiqarish
    double pop () {
        double d = operands_.top ();
        operands_.pop ();
        return d;
    }
    //qiymat qo'shish
    void push (double d) {
        operands_.push (d);
    }
    //tozalash
    void flush () {
        while (! operands_.empty ()) { operands_.pop (); }
    }
    //Agar TOKEN number bo'lsa
    //ushbu funksiya chaqiriladi va yuqorida aytilganidek
    //massivga faqat qiymat qo'shadi
    //[1.1] shart
    void consume(double value) {
        push (value);
    }
    //agar TOKEN funksiya bo'lsa chaqiriladi
    //[1.2] va [1.2.1] shartlar
    void consume(std::string func) {
        if (func == "sin") {
            push(sin(pop())); //[1.2.2] shart
        } else if (func == "max") {
            double v1 = pop();
            double v2 = pop();
            push(v1 > v2 ? v1 : v2); //[1.2.2] shart
        } else if (func == "sqrt") {
            push(sqrt(pop()));
        } else if (func == "cos") {
            push(cos(pop())); //[1.2.2] shart
        } else {
            throw std::domain_error("Funksiya mavjud emas: " + func);
        }
    }
    //Ahar TOKEN operator bo'lsa
    //[1.2] va [1.2.1] shartlar
    void consume(char op) {
        switch (op) {
            case '+':
                push (pop () + pop ()); //[1.2.2] shart
                break;
            case '*':
                push (pop () * pop ()); //[1.2.2] shart
                break;
            case '-':
            {
                double right = pop (); //[1.2.2] shart
                push (pop () - right);
            }
                break;
            case '/':
            {
                double right = pop ();
                if (right == 0)
                    throw std::domain_error("Qiymat 0 ga bo'linyapti");
                push (pop () / right); //[1.2.2] shart
            }
                break;
            case '^':
            {
                double right = pop ();
                push(pow(pop(), right)); //[1.2.2] shart
                break;
            }
            default:
                throw std::domain_error("Operator mavjud emas: " + std::string(1, op));
        }
    }
public:
    Calculator(RpnExpression& rpn) {
        //[1]-shart
        //rpn bo'sh qolguncha TOKEN larga mos
        //funksiyani chaqiramiz
        while(!rpn.empty()) {
            SharedToken t = rpn.pop();
            if (t->isNumber()) {
                consume(t->getNumber());
            } else if (t->isOperator()) {
                consume(t->getOperator());
            } else if (t->isFunction()) {
                consume(t->getFunction());
            }
        }
    }
    double result () const {
        return operands_.top ();
    }
};

Ushbu Calculator obyekti: cos, sin, max, sqrt funksiyalarini va /, -, *, +, ^ amallarini qo'llaydi. Agar xohlasangiz, consume funksiyasiga kengaytirgan holda Calculator ning imkoniyatlarini oshirishingiz mumkin.

Oxirgi sinov:

//code
ShuntingYard shunting("5 * (cos(1) ^ 2 + sin(1) ^ 2) / 2 + 10 - 3 ^ 2 + max(sqrt(25), sqrt(36))");
auto rpn = shunting.getRpn();
rpn.print();
Calculator calc(rpn);
std::cout<<std::endl<<"Natija: "<<calc.result()<<std::endl;
//Natija
RPN: 5 1 cos 2 ^ 1 sin 2 ^ + * 2 / 10 + 3 2 ^ - 25 sqrt 36 sqrt max + 
Natija: 9.5

Yuqoridagi kodda ayrim xatolar hisobga olinmagan bo'lishi mumkin va bu maqola Shunting-yard algoritmi qanday ishlashi haqida tushuncha berish va amalda sinab ko'rish uchun yozildi.

ShuntingYard.cpp

Qo'shimcha ma'lumotlar:

Shunting-yard algorithm

Алгоритм сортировочной станции

Reverse Polish notation

Parsing/Shunting-yard algorithm

Calculator using shunting-yard algorithm


shranet

Muallif haqida

Ruslan Abdullayev Shonazarovich


Blogdagi so‘nggi maqolalar:


Fikrlar 1

abdujabbor1987
abdujabbor1987
xaqiqiy long read bopti!
Iltimos, fikr bildirish uchun saytga kiring yoki ro‘yxatdan o‘ting!