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(T) typedef std::shared_ptr SharedToken; typedef std::vector TokenVector; typedef std::stack 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 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 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::coutstring()
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() precedence() /* 1-shart */) ||
(t->isRightAssociativity() && t->precedence() 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 {
funcgetOperator() == '(')
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 |
| 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 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
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.
Qo'shimcha ma'lumotlar:
Алгоритм сортировочной станции
Algoritm
Shunting-yard algoritmi!