Shunting-yard with functions
// | |
// main.cpp | |
// Texnoman | |
// | |
// Created by Ruslan Abdullaev on 11/23/18. | |
// Copyright © 2018 Ruslan Abdullaev. All rights reserved. | |
// | |
// Post: https://www.texnoman.uz/post/shuntingyard-algoritmi.html | |
#include <iostream> | |
#include <vector> | |
#include <string> | |
#include <map> | |
#include <list> | |
#include <cctype> | |
#include <sstream> | |
#include <stack> | |
#include <memory> | |
#include <cmath> | |
class Token; | |
#define NewToken(T) std::make_shared<Token>(T) | |
typedef std::shared_ptr<Token> SharedToken; | |
typedef std::vector<SharedToken> TokenVector; | |
typedef std::stack<SharedToken> TokenStack; | |
enum TokenTypes { | |
UNDEFINED = 0, | |
NUMBER = 1, | |
FUNCTION = 2, | |
OPERATOR = 3 | |
}; | |
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 ""; | |
} | |
}; | |
//bu ustunlik jadvalini kiritish | |
std::map<char, int> Token::op_precedence_ = { | |
{'(', -1}, | |
{'+', 2}, | |
{'-', 2}, | |
{'*', 3}, | |
{'/', 3}, | |
{'^', 4} | |
}; | |
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; | |
} | |
}; | |
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 not'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 not'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) { | |
} | |
}; | |
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 qo'shiladi | |
//[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 (); | |
} | |
}; | |
int main() { | |
ShuntingYard shunting("5 * (cos(1) ^ 2 + sim(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; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment